# 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))