Is it OK to use log?


  • 1
    T

    Since log(N^2)=2log(N), the problem becomes easy:

    public boolean isPerfectSquare(int num) {
        int sqrt=(int)Math.exp(Math.log(num)/2);
        return sqrt*sqrt == num || (sqrt+1)*(sqrt+1)==num;
    }

  • 0
    A

    I don't think so. While it does state not to use "sqrt" explicitly, it also seems to indicate to not use any built-in library function, which to me would mean any of the math library functions. If you were allowed to do so, you could use power as well:

        bool isPerfectSquare(int num) {
            return int(pow(num,0.5)) != pow(num, 0.5)? false: true;
        }

  • 1

    @adam255 Actually it kind of allows that in a interview, which will enlighten the interviewer that you get quite familiar with the built-in stuff, quite important portfolio here. But I think the more important here is to solve it in a manual way, built-in can be a bonus.

    Typical binary search method

    class Solution {
    public:
        bool isPerfectSquare(int num) 
        {
            long l = 0, r = num, m = 0;
            while(l < r)
            {
                m = l+(r-l)/2;
                if(m*m < num) l = m+1;
                else r = m;
            }
            return r*r==num;
        }
    };
    

    Using Newton method

    class Solution {
    public:
        bool isPerfectSquare(int num) 
        {
            long g = num;
            while(g*g > num) g = (g+num/g)>>1;
            return g*g == num;
        }
    };
    

    B.T.W you guys' solutions are quite original. Awesome, man!


Log in to reply
 

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