A solution that narrows the range of the square root


  • 0
    N

    Find two numbers m1 and m2. m1 * m2 approximate to num. m1 and m2 have the minimal difference.

    public boolean isPerfectSquare(int num) {
        if(num == 1)
            return true;
        int m1 = 1, m2 = num;
        int diff = num - m1;
        do{
            int tmp1 = m1 << 1;
            int tmp2 = m2 >> 1;
            int d = Math.abs(tmp1 - tmp2);
            if(d < diff){
                m1 = tmp1;
                m2 = tmp2;
                diff = d;
            }else{
                break;
            }
        }while(true);
        if(m1 < m2){
            for(int i = m1; i <= m2; i++)
                if(i * i == num)
                    return true;
        }else{
            for(int i = m2; i <= m1; i++)
                if(i * i == num)
                    return true;
        }
        return false;
    }

Log in to reply
 

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