C++ O(logn) code based on Newton's method


  • 2
    class Solution {
    public:
        bool isPerfectSquare(int num) {
            int x = 1;
            int temp = 0;
            
            while (temp != x) {
                temp = x;
                x = round((x + round(num / x)) / 2);
            }
    
            return x * x == num;
        }
    };
    

    Condition in while loop is based on the idea of convergence in Newton's method.


Log in to reply
 

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