906. Super Palindromes

"398904669" "13479046850"
"1" "2"
"96915129" "1492347521772"
"38455498359" "999999999999999999"


Build palindrome
We can build a palindrome by giving a base string and reverse it
e.g.  123 -> 123321 / 12321

We know our input are less than 10^18 -> it's square root are less than 10^9
Since the square root is palindrome concatenated by base str, str is less than 10^5
We iterate over 10^5 and try to build all palindromes R -> check whether R^2 is a palindrome
二刷
58.95 %
class Solution {
    public int superpalindromesInRange(String L, String R) {
        // for any given number x, xr(reversed x)
        // we can build a palindrome by diong xx,x0xr,x1xr,...,x9xr
        int count = 0;
        long min = Long.valueOf(L);
        long max = Long.valueOf(R);
        for (int i = 1; i <= (int)1e5; i++) {
            if (check(i, i, min, max)) count++;
            if (check(i, i / 10, min, max)) count++;
        }
        return count;
    }
    private boolean check(long num, long rev, long min, long max) {
        while (num > 0) {
            rev = rev * 10 + num % 10;
            num /= 10;
        }
        if (rev % 10 >= 4) return false;
        long val = rev * rev;
        if (min <= val && val <= max) {
            return isPalin(val);
        }
        return false;
    }
    private boolean isPalin(long x) {
        long rev = 0;
        if (x != 0 && x % 10 == 0) return false;
        while (rev < x) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev == x || rev / 10 == x;
    }
}

一刷

4.00 %
class Solution {
    public int superpalindromesInRange(String L, String R) {
        int UPPER = (int)(1e5);
        int result = 0;
        long left = Long.valueOf(L);
        long right = Long.valueOf(R);
        // 123 -> 123321 / 12321
        for (int i = 0; i < UPPER; i++) {
            String str = String.valueOf(i);
            String reversedStr = new StringBuffer(str).reverse().toString();
            result += checkPalin(left, right, str + reversedStr) ? 1 : 0;
            result += checkPalin(left, right, str + reversedStr.substring(1)) ? 1 : 0;
        }
        return result;
    }

    private boolean checkPalin(long left, long right, String palin) {
        long value = Long.valueOf(palin);
        value *= value;
        if (left <= value && value <= right && isPalindrome(value)) {
            return true;
        }
        return false;
    }

    private boolean isPalindrome(long x) {
        long temp = x;
        long reverse = 0;
        while (temp > 0) {
            reverse = reverse * 10 + temp % 10;
            temp /= 10;
        }
        return x == reverse;
    }
}