package leetcode;

/**
 * https://leetcode.com/problems/valid-perfect-square/
 */
public class Problem367 {
    public boolean isPerfectSquare(int num) {
        double sqrt = sqrt(num);
        double diff = Math.abs((int) sqrt - sqrt);
        System.out.println("diff: " + diff + " --> " + sqrt + " --> " + (int) (diff * 100));
        // TODO:
        return (int) (diff * 100) <= 5;
    }

    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));
    }
}

@@ -180,16 +180,104 @@
 t(num);%0A
+        int isqrt = (int) sqrt(num);%0A        System.out.println(sqrt + %22 vs %22 + isqrt);%0A
         
@@ -315,24 +315,26 @@
 rt - sqrt);%0A
+//
         Syst
@@ -1209,18 +1209,16 @@
 m367();%0A
-//
         
@@ -1260,26 +1260,24 @@
 uare(100));%0A
-//
         Syst
@@ -1313,26 +1313,24 @@
 Square(4));%0A
-//
         Syst
@@ -1366,26 +1366,24 @@
 Square(3));%0A
-//
         Syst
@@ -1420,26 +1420,24 @@
 quare(25));%0A
-//
         Syst
@@ -1474,26 +1474,24 @@
 quare(26));%0A
-//
         Syst
@@ -1533,18 +1533,16 @@
 (681));%0A
-//
         

Update problem 367