Problem

You have n fair coins and you flip them all at the same time. Any that come up tails you set aside. The ones that come up heads you flip again. How many rounds do you expect to play before only one coin remains?

Write a function that, given n, returns the number of rounds you’d expect to play until one coin remains.

Examples

Example 1

Input: n = 1
Output: 0
Explanation: With one coin, no flipping is needed as it is already the only one.

Example 2

Input: n = 2
Output: 1
Explanation: Two coins flipped once would result in one coin expected to be heads, which becomes the only remaining coin.

Solution

Method 1 - Numerical

In each round of flipping the coins, about half of the coins will come up heads (since each flip is an independent event with a 50% chance). We can estimate the number of rounds required to reduce n coins to one remaining coin by repeatedly reducing the number of coins by half.

Approach

  1. Mathematical Insight: In each round, the number of remaining coins is expected to halve.
  2. Number of Rounds: This process continues until only one coin remains. The number of rounds required to reduce n to 1 can be estimated using the logarithm base 2 of n.
  3. Return Value: For an integer n, the expected number of rounds required is the ceiling value of the logarithm base 2 of n.

Code

Java
public class Solution {
    public int expectedRounds(int n) {
        return (int) Math.ceil(Math.log(n) / Math.log(2));
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.expectedRounds(1)); // Output: 0
        System.out.println(solution.expectedRounds(2)); // Output: 1
        System.out.println(solution.expectedRounds(4)); // Output: 2
        System.out.println(solution.expectedRounds(10)); // Output: 4
    }
}
Python
import math

class Solution:
    def expectedRounds(self, n: int) -> int:
        return math.ceil(math.log(n, 2))

# For testing the solution
if __name__ == "__main__":
    solution = Solution()
    print(solution.expectedRounds(1))  # Output: 0
    print(solution.expectedRounds(2))  # Output: 1
    print(solution.expectedRounds(4))  # Output: 2
    print(solution.expectedRounds(10)) # Output: 4

Complexity

  • ⏰ Time complexity: O(1) - The computation of the logarithm is essentially constant time.
  • 🧺 Space complexity: O(1) - Only a small fixed amount of space is required for the calculation.