O(log n) solution without using sqrt


  • 0
    C
    class Solution {
    public:
    
        bool ips(int start, int end, int num)
        {
            if(start > end)
            {
                return false;
            }
            int mid = start + (end-start)/2;
            long long hold = (long long) mid;
            long long square = hold*hold;
            if(square == num)
            {
                return true;
            }
            if(square > num)
            {
                return ips(start,mid-1,num);
            }
            else
            {
                return ips(mid+1,end,num);
            }
            
            
        }
    
        bool isPerfectSquare(int num) {
            return ips(0,num,num);
            
            
        }
    };

Log in to reply
 

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