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) {
    // The k-th bulb can only be switched when k % i == 0.
    // So, we can rephrase the problem:
    // To find number of numbers <= 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) {
    // The k-th bulb can only be switched when k % i == 0.
    // So, we can rephrase the problem:
    // To find number of numbers <= 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
4
5
6
7
8
class Solution:
  def bulbSwitch(self, n: int) -> int:
    # The k-th bulb can only be switched when k % i == 0.
    # So, we can rephrase the problem:
    # To find number of numbers <= 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 math.isqrt(n)