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 ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
Example 1:
Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1 because there is only one bulb is on.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 1
Constraints:
0 <= n <= 109In this approach, we observe that bulbs that remain on are those that are toggled an odd number of times. Typically, a bulb indexed at i is toggled once for every divisor it has. Numbers which are perfect squares have an odd number of divisors (since one of its divisors is repeated, for example, the square root). Hence, the number of bulbs that will remain on is determined by the number of perfect squares up to n. Therefore, the number of bulbs left on is the integer part of the square root of n.
The solution uses the math library to calculate the square root of n and casts it to an integer, thereby getting the count of perfect squares less than or equal to n.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) as computing the square root and type casting are constant time operations.
Space Complexity: O(1) since no additional space is used.
This approach involves explicitly counting all perfect squares up to n by probing through potential perfect squares. Starting from 1, we continue as long as i*i is less than or equal to n, incrementing the counter each time. This direct enumeration is straightforward and still only traverses a limited range due to the root domain.
Iterate with a simple for-loop, counting perfect squares by incrementing the square root, i, until i*i surpasses n.
C++
Java
Python
C#
JavaScript
Time Complexity: O(√n), iterates through the square roots from 1 to √n.
Space Complexity: O(1) uses fixed amount of additional space.
| Approach | Complexity |
|---|---|
| Perfect Square Insight | Time Complexity: O(1) as computing the square root and type casting are constant time operations. |
| Counting Perfect Squares by Iteration | Time Complexity: O(√n), iterates through the square roots from 1 to √n. |
Bulb Switcher (Leetcode 319) - Medium (Hindi) • The Hustling Engineer • 9,475 views views
Watch 9 more video solutions →Practice Bulb Switcher with our built-in code editor and test cases.
Practice on FleetCode