c++ math, binary search (O(log(n)))


  • 0

    1) Math
    num = x ^ 2
    2 = log_x(num)
    2 = log_y(num) / log_y(x)
    log_y(x) = log_y(num) / 2
    x = 10 ^ (log_y(num) / 2)
    if x * x equals num that means we have perfect square
    time complexity: O(log(n))

    bool isPerfectSquare(int num) {
        int x = round(pow(10, log10(num) / 2));
        return x * x == num;
    }
    

    2) Binary search
    time complexity: O(log(n))

    bool isPerfectSquare(int num) {
        long long l = 0, r = num;
        while (l <= r) {
            long long mid =  l + (r - l) / 2;
            if (mid * mid == num) return true;
            if (mid * mid > num) r = mid - 1;
            else l = mid + 1;
        }
        return (num == 1) ? true : false;
    }
    

Log in to reply
 

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