[Java/C++/Python] All Even Length Palindrome are Divisible by 11
Intuition\nWrite some example, you find all even length palindromes are divisible by 11.\nSo we need to search only palindrome with odd length.\n\nWe can prove 
# **Intuition**\nWrite some example, you find all even length palindromes are divisible by 11.\nSo we need to search only palindrome with odd length.\n\nWe can prove as follow:\n11 % 11 = 0\n1111 % 11 = 0\n111111 % 11 = 0\n11111111 % 11 = 0\n\n**So:**\n1001 % 11 = (1111 - 11 * 10) % 11 = 0\n100001 % 11 = (111111 - 1111 * 10) % 11 = 0\n10000001 % 11 = (11111111 - 111111 * 10) % 11 = 0\n\nFor any palindrome with even length:\nabcddcba % 11\n= (a * 10000001 + b * 100001 * 10 + c * 1001 * 100 + d * 11 * 1000) % 11\n= 0\n\nAll palindrome with even length is multiple of `11`.\nSo among them, 11 is the only one prime\n`if (8 <= N <= 11) return 11`\n\nFor other cases, **we consider only palindrome with odd dights.**\n<br>\n\n# More Generally\nExplanation from @chuan-chih:\nA number is divisible by 11 if `sum(even digits) - sum(odd digits)` is divisible by 11.\n**Base case: 0**\n**Inductive step:**\nIf there is no carry when we add 11 to a number, both sums +1.\nWhenever carry happens, one sum -10 and the other +1.\nThe invariant holds in both cases.\n<br>\n\n# **Time Complexity**\n`O(10000)` to check all numbers 1 - 10000.\n`isPrime` function is `O(sqrt(x))` in worst case.\nBut only `sqrt(N)` worst cases for `1 <= x <= N`\nIn general it\'s `O(logx)`\n<br>\n\n**C++:**\n```cpp\n    int primePalindrome(int N) {\n        if (8 <= N && N <= 11) return 11;\n        for (int x = 1; x < 100000; ++x) {\n            string s = to_string(x), r(s.rbegin(), s.rend());\n            int y = stoi(s + r.substr(1));\n            if (y >= N && isPrime(y)) return y;\n        }\n        return -1;\n    }\n    bool isPrime(int num) {\n        if (num < 2 || num % 2 == 0) return num == 2;\n        for (int i = 3; i * i <= num; i += 2)\n            if (num % i == 0) return false;\n        return true;\n    }\n```\n\n**Java:**\n```java\n    public int primePalindrome(int N) {\n        if (8 <= N && N <= 11) return 11;\n        for (int x = 1; x < 100000; x++) {\n            String s = Integer.toString(x), r = new StringBuilder(s).reverse().toString();\n            int y = Integer.parseInt(s + r.substring(1));\n            if (y >= N && isPrime(y)) return y;\n        }\n        return -1;\n    }\n\n    public Boolean isPrime(int x) {\n        if (x < 2 || x % 2 == 0) return x == 2;\n        for (int i = 3; i * i <= x; i += 2)\n            if (x % i == 0) return false;\n        return true;\n    }\n```\n\n\n**Python:**\n```py\n    def primePalindrome(self, N):\n        def isPrime(x):\n            if x < 2 or x % 2 == 0: return x == 2\n            for i in xrange(3, int(x**0.5) + 1, 2):\n                if x % i == 0: return False\n            return True\n        if 8 <= N <= 11: return 11\n        for x in xrange(10 ** (len(str(N)) / 2), 10**5):\n            y = int(str(x) + str(x)[-2::-1])\n            if y >= N and isPrime(y): return y\n```
[]