package com.freetymekiyan.algorithms.level.medium;

import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Given a positive integer num, write a function which returns True if num is a perfect square else False.
 * <p>
 * Note: Do not use any built-in library function such as sqrt.
 * <p>
 * Example 1:
 * <p>
 * Input: 16
 * Returns: True
 * Example 2:
 * <p>
 * Input: 14
 * Returns: False
 * <p>
 * Tags: Binary Search, Math
 * Similar Problems: (M) Sqrt(x)
 */
public class ValidPerfectSquare {

    private ValidPerfectSquare v;

    /**
     * Binary Search.
     * The original thought is binary search from 1 to sqrt(n).
     * Since we cannot use built-in library, we use n / 2 to replace it.
     * Note that n / 2 > sqrt(n) when n > 4.
     */
    public boolean isPerfectSquare(int num) {
        if (num < 4) {
            return num == 1;
        }
        int l = 1;
        int r = num / 2;
        while (l <= r) {
            int m = l + (r - l) / 2;
            long t = m * m;
            if (t == num) {
                return true;
            } else if (t > num) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return false;
    }

    /**
     * Math.
     * A perfect square is the sum of a consecutive odd number sequence.
     * 1 + 3 + 5 + 7 + 9 ...
     * For example: 1 = 1, 4 = 1 + 3, 9 = 1 + 3 + 5, 16 = 1 + 3 + 5 + 7
     */
    public boolean isPerfectSquareB(int num) {
        int i = 1;
        while (num > 0) {
            num -= i;
            i += 2;
        }
        return num == 0;
    }

    /**
     * Math, Newton's Method.
     * x(n+1) = x(n) - f(x(n)) / f'(x(n))
     * Find the root for y = num - t^2.
     * t - (num - t^2) / -2t = t + num / 2t - t / 2 = (t + num / t) / 2
     * https://en.wikipedia.org/wiki/Newton%27s_method
     */
    public boolean isPerfectSquareC(int num) {
        long t = num;
        while (t * t > num) {
            t = (t + num / t) / 2;
        }
        return t * t == num;
    }

    @Before
    public void setUp() {
        v = new ValidPerfectSquare();
    }

    @Test
    public void testExamples() {
        int num = 16;
        Assert.assertTrue(v.isPerfectSquare(num));
        Assert.assertTrue(v.isPerfectSquareB(num));
        Assert.assertTrue(v.isPerfectSquareC(num));
        num = 14;
        Assert.assertFalse(v.isPerfectSquare(num));
        Assert.assertFalse(v.isPerfectSquareB(num));
        Assert.assertFalse(v.isPerfectSquareC(num));
        num = 1;
        Assert.assertTrue(v.isPerfectSquare(num));
        Assert.assertTrue(v.isPerfectSquareB(num));
        Assert.assertTrue(v.isPerfectSquareC(num));
        num = 2;
        Assert.assertFalse(v.isPerfectSquare(num));
        Assert.assertFalse(v.isPerfectSquareB(num));
        Assert.assertFalse(v.isPerfectSquareC(num));
        num = 3;
        Assert.assertFalse(v.isPerfectSquare(num));
        Assert.assertFalse(v.isPerfectSquareB(num));
        Assert.assertFalse(v.isPerfectSquareC(num));
        num = 4;
        Assert.assertTrue(v.isPerfectSquare(num));
        Assert.assertTrue(v.isPerfectSquareB(num));
        Assert.assertTrue(v.isPerfectSquareC(num));
        num = 5;
        Assert.assertFalse(v.isPerfectSquare(num));
        Assert.assertFalse(v.isPerfectSquareB(num));
        Assert.assertFalse(v.isPerfectSquareC(num));
    }

    @After
    public void tearDown() {
        v = null;
    }

}

@@ -443,16 +443,42 @@
 %0A * %3Cp%3E%0A
+ * Company Tags: LinkedIn%0A
  * Tags:
@@ -817,16 +817,329 @@
  n %3E 4.%0A
+     * The initial range is from 1 to num / 2.%0A     * For each middle value m, compare t = m * m and num.%0A     * %7C If t == num, return true.%0A     * %7C If t %3E num, m is too big, reduce upper bound r = m - 1.%0A     * %7C If t %3C num, m is too small, increase lower bound l = m + 1.%0A     * Return false if search failed.%0A
      */%0A
@@ -1259,16 +1259,17 @@
    int l
+o
  = 1;%0A  
@@ -1278,17 +1278,18 @@
     int 
-r
+hi
  = num /
@@ -1312,13 +1312,15 @@
 e (l
+o
  %3C= 
-r
+hi
 ) %7B%0A
@@ -1335,26 +1335,32 @@
     
-int m
+long mid
  = l
+o
  + (
-r
+hi
  - l
+o
 ) / 
@@ -1388,13 +1388,50 @@
  = m
+id
  * m
-;
+id; // Might overflow. num = 808021.
 %0A   
@@ -1534,21 +1534,30 @@
         
-r = m
+hi = (int) mid
  - 1;%0A  
@@ -1592,20 +1592,29 @@
        l
+o
  = 
-m
+(int) mid
  + 1;%0A  
@@ -3822,24 +3822,201 @@
 areC(num));%0A
+        num = 808201;%0A        Assert.assertTrue(v.isPerfectSquare(num));%0A        Assert.assertTrue(v.isPerfectSquareB(num));%0A        Assert.assertTrue(v.isPerfectSquareC(num));%0A
     %7D%0A%0A    @

update Valid Perfect Square