Skip to content

319. Bulb Switcher 👎

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  int bulbSwitch(int n) {
    // K-th bulb only be switched when k % i == 0.
    // So we can reiterate the problem:
    // To find # of number <= n that have odd factors.
    // Obviously, only square numbers have odd factor(s).
    // E.g. n = 10, only 1, 4, and 9 are square numbers that <= 10
    return sqrt(n);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
  public int bulbSwitch(int n) {
    // K-th bulb only be switched when k % i == 0.
    // So we can reiterate the problem:
    // To find # of number <= n that have odd factors.
    // Obviously, only square numbers have odd factor(s).
    // E.g. n = 10, only 1, 4, and 9 are square numbers that <= 10
    return (int) Math.sqrt(n);
  }
}

1
2
3
class Solution:
  def bulbSwitch(self, n: int) -> int:
    return int(sqrt(n))