Problem Description
There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Return the number of bulbs that are on after n rounds.
Key Insights
- Each bulb's state is toggled on rounds that are multiples of its index.
- A bulb will end up being on if it is toggled an odd number of times.
- The number of times a bulb at index k is toggled corresponds to the number of divisors k has.
- Only perfect squares have an odd number of divisors (e.g., 1, 4, 9, 16, ...).
- Therefore, the number of bulbs that remain on is equal to the largest integer k such that k^2 ≤ n, which is the integer part of the square root of n.
Space and Time Complexity
Time Complexity: O(1) - The solution involves a constant-time calculation of the square root. Space Complexity: O(1) - No additional space is required.
Solution
The solution involves calculating the largest integer k such that k^2 is less than or equal to n. This can be efficiently computed using the square root function.