Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

319. Bulb Switcher

Time: $O(1)$

Space: $O(1)$

			


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);
  }
};




			


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);
  }
}




			


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