algoadvance

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 it on if it’s off or off if it’s on). For the i-th round, you toggle every i-th bulb. For the n-th round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

Example:

Input: n = 3
Output: 1

Explanation: 
Initially, the bulb states are [off, off, off].
After the first round, the bulb states are [on, on, on].
After the second round, the bulb states are [on, off, on].
After the third round, the bulb states are [on, off, off].

So you should return 1 because there is only one bulb that is on.

Clarifying Questions

1. What is the maximum value of n?
   • While the problem does not explicitly mention the constraints, it would be valuable to understand if there are any practical limits.
2. Is performance a concern?
   • Clarifying if there are any performance constraints can help define if an optimized solution is required.

Strategy

To determine which bulbs are on after n rounds:

• The state of each bulb toggles in every round in which the bulb number is a multiple of the round number. For example, bulb number 6 will be toggled in rounds 1, 2, 3, and 6.
• A bulb ends up being on if it is toggled an odd number of times.
• A bulb i is toggled in the j-th round if and only if j is a divisor of i.
• i has an odd number of divisors if and only if i is a perfect square. This is because divisors generally come in pairs, except when they are the square root of the number.

Therefore, the number of bulbs that remain on after n rounds is the count of perfect squares less than or equal to n. The perfect squares less than or equal to n are 1, 4, 9, ..., k^2 where k^2 <= n.

The number of such perfect squares is the largest integer k such that k^2 <= n, which is floor(sqrt(n)).

Code

import math

def bulbSwitch(n: int) -> int:
    return int(math.sqrt(n))

Time Complexity

• Time Complexity: The solution involves calculating sqrt(n) which is an O(1) operation.
• Auxiliary Space Complexity: The required space is also O(1) since we are only storing a single integer result.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?