My 0 ms C++ solution with explanation


  • 49
    L
    int bulbSwitch(int n) {
        int counts = 0;
        
        for (int i=1; i*i<=n; ++i) {
            ++ counts;    
        }
        
        return counts;
    }
    

    Explanation:
    A light will be toggled only during the round of its factors, e.g. number 6 light will be toggled at 1,2,3,6 and light 12 will be toggled at 1,2,3,4,6,12. The final state of a light is on and off only depends on if the number of its factor is odd or even. If odd, the light is on and if even the light is off. The number of one number's factor is odd if and only if it is a perfect square!
    So we will only need to loop to find all the perfect squares that are smaller than n!


  • 0
    Y

    could you explain a bit why "number of one number's factor is odd if and only if it is a perfect square"?


  • 1
    N

    Take 18 and 16 as an example: 18 has factor pairs of [1,18], [2,9], [3,6] while 16 as factor pairs of [1,16], [2,8], [4], as you can see, perfect squares will always have a factor pair that contains only one number which makes it perfect squares.


  • 0
    Y

    Thank you and it really helped.


  • 0
    I

    try 2147483647.


  • 0
    C

    I tried this and found it is not faster than sqrt. That's weird. I bet binary search should work better. However, the binary search code got some runtime error when n is large enough.

    public int bulbSwitch(int n) {
           int low = 0, high = n + 1;
            int mid;
            while(high - low > 1){
                mid = ((high - low) >> 1) + low;
                if(mid * mid <= n) low = mid;
                else high = mid ;
            }
            return low ;
            //return (int) Math.sqrt(n);
        }

  • 0
    S

    use long and cast to int


  • 0
    C

    I would just hard code the const of sqrt(Integer.MAX_VALUE) as the upper bound.


  • 0
    B

    both methods cost 0ms, I think binary search is faster, too.

    int bulbSwitch(int n) {
        long long lo = 0, hi = n, mid;
        while (lo < hi) {
            mid = lo + (hi - lo + 1) / 2;
            if (mid * mid <= n)
                lo = mid;
            else
                hi = mid - 1;
        }
        return lo;
    }
    

  • 0
    T

    when n = 200K, mid * mid = 10G, this is larger than max integer, so it causes runtime error. You can calculate bits of n in O(logn) time, then let high = 1 << (bits / 2 + 2) and use binary search as you did. It takes O(logn).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.