package buildingblock.table.hashing.lc202_happynumber;

import java.util.HashSet;
import java.util.Set;

/**
 * Write an algorithm to determine if a number is "happy".
 * A happy number is a number defined by the following process:
 * Starting with any positive integer, replace the number by the sum of the squares of its digits,
 * and repeat the process until the number equals 1 (where it will stay),
 * or it loops endlessly in a cycle which does not include 1.
 * Those numbers for which this process ends in 1 are happy numbers.
 * Example: 19 is a happy number
 *  1^2 + 9^2 = 82
 *  8^2 + 2^2 = 68
 *  6^2 + 8^2 = 100
 *  1^2 + 0^2 + 0^2 = 1
 */
public class Solution {

    // An interesting "find cycle in linked list" flavour solution
    public boolean isHappy(int n) {
        int slow = n, fast = n;
        // eg. 10, slow=1, fast=1, wrong!
        /*while (slow != 1) {
            slow = next(slow);
            fast = next(next(fast));
            if (slow == fast) {
                return false;
            }
        }*/
        do {
            slow = next(slow);
            fast = next(next(fast));
        } while (slow != fast);
        return slow == 1;
    }

    private int next(int n) {
        int sum = 0;
        while (n > 0) {
            int d = (n % 10);
            sum += d * d;
            n /= 10;
        }
        return sum;
    }

    // My 2nd
    public boolean isHappy2(int n) {
        if (n <= 0) {
            return false;
        }

        Set<Integer> nums = new HashSet<>();
        while (n != 1) {
            int sum = 0;
            while (n > 0) {
                int d = (n % 10);
                sum += d * d;
                n /= 10;
            }
            n = sum;

            // Infinite dead loop
            if (!nums.add(n)) {     // Simplied!
                return false;
            }
        }

        // n = 1
        return true;
    }

    // My 1st
    public boolean isHappy1(int n) {
        if (n <= 0) {
            return false;
        }

        Set<Integer> nums = new HashSet<>();
        while (n != 1) {
            if (nums.contains(n)) {
                return false;
            }
            nums.add(n);

            int next = 0;
            while (n > 0) {
                int tmp = n % 10;
                next += (tmp * tmp);
                n /= 10;
            }
            n = next;
        }
        return true;
    }

}

@@ -673,16 +673,1086 @@
 tion %7B%0A%0A
+    // O(N) space%0A    public boolean isHappy(int n) %7B%0A        if (n %3C= 0) return false;%0A        Set%3CLong%3E seen = new HashSet%3C%3E();%0A        for (long l = n, tmp = 0; l != 1; l = tmp, tmp = 0) %7B%0A            if (!seen.add(l)) %7B%0A                return false;%0A            %7D%0A            for (; l %3E 0; l /= 10) %7B%0A                long d = l %25 10;%0A                tmp += d * d;%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A    // O(1) space by Floyd%E2%80%99s Cycle-Finding Algorithm%0A    // eg. n=19  slow  fast%0A    //            82    68%0A    //            68     1%0A    //           100     1%0A    //             1     1%0A    public boolean isHappy_floyd(int n) %7B%0A        if (n %3C= 0) return false;%0A        int slow = n, fast = n;%0A        do %7B%0A            slow = next(slow);%0A            fast = next(next(fast));%0A        %7D while (slow != fast);%0A        return slow == 1; // Find cycle, check if cycle only contains 1%0A    %7D%0A%0A    private int next(int n) %7B%0A        int ret = 0;%0A        for (; n %3E 0; n /= 10) %7B%0A            ret += Math.pow(n %25 10, 2);%0A        %7D%0A        return ret;%0A    %7D%0A%0A
     // A
@@ -1828,32 +1828,34 @@
  boolean isHappy
+21
 (int n) %7B%0A      
@@ -2266,32 +2266,34 @@
 private int next
+21
 (int n) %7B%0A      

happy number