package leetcode;

/**
 * https://leetcode.com/problems/valid-perfect-square/
 */
public class Problem367 {
    public boolean isPerfectSquare(int num) {
        double sqrt = sqrt(num);
        int isqrt = (int) sqrt;
        return (isqrt * isqrt) == num;
    }

    private double sqrt(int x) {
        // using Newton's method
        // https://www.youtube.com/watch?v=2158QbsunA8
        double sqrt = sqrt(x, x);
        while (true) {
            double tmp = sqrt;
            sqrt = sqrt(sqrt, x);
            if (Double.isNaN(sqrt) || tmp - sqrt < 1) {
                break;
            }
        }
        return sqrt;
    }

    private double fx(double x, double y) {
        return (x * x) - y;
    }

    private double dfx(double x) {
        // the derivative of fx
        return 2 * x;
    }

    private double sqrt(double x, double y) {
        return x - (fx(x, y) / dfx(x));
    }

    public static void main(String[] args) {
        Problem367 prob = new Problem367();
        System.out.println(prob.isPerfectSquare(100));
        System.out.println(prob.isPerfectSquare(4));
        System.out.println(prob.isPerfectSquare(3));
        System.out.println(prob.isPerfectSquare(25));
        System.out.println(prob.isPerfectSquare(26));
        System.out.println(prob.isPerfectSquare(681));
        System.out.println(prob.isPerfectSquare(36));
        System.out.println(prob.isPerfectSquare(362));
    }
}

@@ -902,536 +902,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem367 prob = new Problem367();%0A        System.out.println(prob.isPerfectSquare(100));%0A        System.out.println(prob.isPerfectSquare(4));%0A        System.out.println(prob.isPerfectSquare(3));%0A        System.out.println(prob.isPerfectSquare(25));%0A        System.out.println(prob.isPerfectSquare(26));%0A        System.out.println(prob.isPerfectSquare(681));%0A        System.out.println(prob.isPerfectSquare(36));%0A        System.out.println(prob.isPerfectSquare(362));%0A    %7D
 %0A%7D%0A

Update problem 367