package miscellaneous.math.number.lc008_palindromenumber;

/**
 * Determine whether an integer is a palindrome. Do this without extra space.
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().isPalindrome(12321));
    }

    // Amazing solution from cbmbbz
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) { // Note 10..00 will cause half=0, but 0 is palindrome
            return false;
        }
        // Reverse half of digits, no need to worry about overflow
        int half = 0;
        while (half < x) {
            half = half * 10 + x % 10;
            x /= 10;
        } /* half >= x */
        return half == x || half / 10 == x;
    }

    // My 2nd: Wrong! It's very hard to get each digit for decimal not binary
    public boolean isPalindrome_wrong(int x) {
        if (x < 0) {
            return false;
        }

        int high = 1;
        while (high * 10 <= x) {
            high *= 10;
        }
        /* high * 10 > x */

        for (int low = 10; low < high; low *= 10, high /= 10) {
            //if (((x >> (low - 1)) & 1) != ((x >> (high - 1)) & 1)) { // error: it's binary
            if ((x / high) != (x % low)) {
                return false;
            }
        }
        return true;
    }

    // My 1AC
    public boolean isPalindrome1(int x) {
        if (x < 0) {
            return false;
        }

        int d = 1;
        while (x / d >= 10) {
            d = d * 10;
        }

        while (x > 0) {
            int h = x / d;
            int l = x % 10;
            if (h != l) {
                return false;
            }
            x = (x % d) / 10;
            d = d / 100;     // error: x miss high and low digit, so d /= 100 rather than 10
        }
        return true;
    }

    public boolean isPalindrome2(int x) {
        if (x < 0) {
            return false;
        }
        if (x < 10) { // error2
            return true;
        }

        int y = 0, diff = -1; // error1: diff should init as -1 nor 0
        while (x > 0 && !(x == y || (0 <= diff && diff < 10))) {
            y = y * 10 + x % 10;
            x = x / 10;
            diff = x - y * 10;
        }
        return (x != 0);
    }

}

@@ -275,24 +275,520 @@
 1));%0A    %7D%0A%0A
+    // Same idea as Reverse Integer but only check half way to avoid overflow%0A    // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99%0A    // 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202%0A    public boolean isPalindrome(int x) %7B%0A        if (x %3C 0 %7C%7C (x != 0 && x %25 10 == 0)) return false; // tricky edge case%0A        int rev = 0;%0A        while (x %3E rev) %7B%0A            rev = rev * 10 + x %25 10;%0A            x /= 10;%0A        %7D%0A        return rev == x %7C%7C rev / 10 == x;%0A    %7D%0A%0A
     // Amazi
@@ -834,32 +834,33 @@
 ean isPalindrome
+3
 (int x) %7B%0A      

palindrome number