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

  • 0
    class Solution {
        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;
                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.