[Java] Iterate odd-length palindromes; Generate next palindrome. Beats 100%
Iterate odd-length palindromes\n\nPrerequisite knowledge: Divisibility Rule of 11\nA number is divisible by 11 iff difference between sum of its odd digits (i.e
**Iterate odd-length palindromes**\n\nPrerequisite knowledge: [Divisibility Rule of 11](https://en.wikipedia.org/wiki/Divisibility_rule)\nA number is divisible by 11 iff difference between sum of its odd digits (i.e. digits at odd places) and sum of its even digits is divisible by 11.\n\nThis implies that all even-length palindromes are divisible by 11 since sum(odd digits) = sum(even digits). So even-length palindromes can not be primes except the number 11 itself.\n\nSo we skip even-length palindromes and iterate only over odd-length palindromes to look for primes. Iterating palindromes sequentially means iterating over their left half and appending the reverse of the left half as right half to construct the palindrome.\n\n```\n// 5 ms. 99.03%\nclass Solution {\n    private int makePalindrome(int n) {\n        int p = n;\n        while((n /= 10) != 0)\n            p = p * 10 + n % 10;\n        return p;\n    }\n    private boolean isPrime(int n) {\n        if(n % 2 == 0) return n == 2;\n        for(int i = 3, s = (int) Math.sqrt(n); i <= s; i += 2)\n            if(n % i == 0) return false;\n        return true;\n    }\n    public int primePalindrome(int N) {\n        if(N >= 8 && N <= 11) return 11;\n        for(int i = 2; i < 100000; i++) {\n            int p = makePalindrome(i);\n            if(p >= N && isPrime(p)) return p;\n        }\n        return -1;\n    }\n}\n```\n\n**Generate next palindrome**\n\nWe can borrow our knowledge from [564. Find the Closest Palindrome](https://leetcode.com/problems/find-the-closest-palindrome/discuss/960052/Find-previous-and-next-palindromes-detailed-explanation) to calculate next palindrome from a number. Another problem that can be solved using next palindrome idea: [906. Super Palindromes](https://leetcode.com/problems/super-palindromes/discuss/1198415/Java-Build-next-palindrome-Solve-2-Hards)\n\n```\n// 1 ms. 100%\nclass Solution {\n    private boolean isPrime(int n) {\n        if(n % 2 == 0) return n == 2;\n        for(int i = 3, s = (int) Math.sqrt(n); i <= s; i += 2)\n            if(n % i == 0) return false;\n        return true;\n    }\n    private int next(int num) {\n        char[] s = String.valueOf(num + 1).toCharArray();\n        for(int i = 0, n = s.length; i < (n >> 1); i++) {\n            while(s[i] != s[n - 1 - i]) {\n                increment(s, n - 1 - i);\n            }\n        }\n        return Integer.parseInt(new String(s));\n    }\n    private void increment(char[] s, int i) {\n        while(s[i] == \'9\') s[i--] = \'0\';\n        s[i]++;\n    }\n    public int primePalindrome(int N) {\n        if(N <= 2) return 2;\n        int p = next(N - 1);\n        while(!isPrime(p)) {\n            if(10_000_000 <= p && p < 100_000_000)\n                p = 100_000_000;\n            p = next(p);\n        }\n        return p;\n    }\n}\n```\n\nNote that ``` if(10_000_000 <= p && p < 100_000_000) p = 100_000_000; ``` is just an optimization to skip over even-length numbers of length 8. Even if we remove these lines, the code runs in ```8 ms. 97.10%``` which isn\'t too bad.
[]