Sponsored
Sponsored
In 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.
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.
1class Solution {
2 public int bulbSwitch(int n) {
3 return (int)Math.sqrt(n);
4 }
5}The Math.sqrt method computes the square root of n, and it's cast to an integer to get the count of the bulbs that remain on.
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.
Time Complexity: O(√n), iterates through the square roots from 1 to √n.
Space Complexity: O(1) uses fixed amount of additional space.
1This Python method employs a while loop to explore the number of i values satisfying i * i ≤ n, effectively counting perfect squares below n.