My C++ solution (binary search the max x that x*x<=n)


  • 0
    D
    class Solution {
    public:
        int bulbSwitch(int n) {
            //Basically, it is equivalent to find the largest integer x that x^2<=n (i.e x= int(sqrt(n)); ) using binary search
            int left=2, right=n, mid;
            if(n<=0) return 0;
            while(left<right)
            {
                mid = (left+right)>>1;
                if(mid<=n/mid) left = mid+1;
                else right = mid;
            }
            return left-1;
        }
    }
    

    ;


Log in to reply
 

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