LeetCode 866 - Prime Palindrome

https://leetcode.com/problems/prime-palindrome/

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it's only divisors are 1 and itself, and it is greater than 1. 

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left. 

For example, 12321 is a palindrome. 

Let's investigate and improve on a brute force method.

With basic methods, we can check whether an integer $N$ is a palindrome in $O(\log N)$ time, and check whether it is prime in $O(\sqrt{N})$ time. So we would probably like to do the palindrome check first.

Now, say we naively check every number $N, N+1, \cdots, N+K$. How big is $K$?

Well, the palindromes could be approximately $10^4$ apart, since for example 99988999's next palindrome is 99999999.

Say we have a palindrome $X$. What is the next palindrome?

Each palindrome of $d$ digits has a palindromic root, it's first $k = \frac{d+1}{2}$ digits. The next palindrome is formed by the next root.

For example, if $123$ is a root for the 5 digit palindrome $12321$, then the next palindrome is $12421$ with root $124$.

Notice that roots and palindromes are not a bijection, as palindromes $123321$ and $12321$ have the same root.

Algorithm

For each palindromic root, let's find the two associated palindromes (one with an odd number of digits, and one with an even number.) For roots with $k$ digits, they will generate palindromes of $2*k - 1$ and $2*k$ digits.

If we didn't know that palindromes with an even number of digits (and greater than 11) are never prime, we're still fine - we can just check both possibilities. When checking both possibilities, we check the palindromes with $2k - 1$ digits first, as they are all smaller than the palindromes with $2k$ digits.

We'll use an idea from [LeetCode Problem: Reverse an Integer], in order to check whether an integer is a palindrome. We could have also converted the integer to a string, and checked the indices directly.

As for testing primes with isPrime(N), we'll use the standard $O(\sqrt{N})$ check: testing whether every number $\leq \sqrt{N}$ is a divisor of $N$.

• Time Complexity: Based on our analysis above, we performed on the order of $O(N)$ operations (not counting log factors from dealing with integers), given we knew the existence of prime palindrome 100030001.
  Interestingly, the time complexity is an open problem in mathematics, as it is not even known whether there are infinitely many prime palindromes, or whether palindromes behave as random integers for our purposes here - see ["Almost All Palindromes are Composite"] for more.
• Space Complexity: $O(\log N)$, the space used by s (or sb in Java.) 

  public int primePalindrome(int N) {

    for (int L = 1; L <= 5; ++L) {

      // Check for odd-length palindromes

      for (int root = (int) Math.pow(10, L - 1); root < (int) Math.pow(10, L); ++root) {

        StringBuilder sb = new StringBuilder(Integer.toString(root));

        for (int k = L - 2; k >= 0; --k)

          sb.append(sb.charAt(k));

        int x = Integer.valueOf(sb.toString());

        if (x >= N && isPrime(x))

          return x;

        // If we didn't check for even-length palindromes:

        // return N <= 11 ? min(x, 11) : x

      }

      // Check for even-length palindromes

      for (int root = (int) Math.pow(10, L - 1); root < (int) Math.pow(10, L); ++root) {

        StringBuilder sb = new StringBuilder(Integer.toString(root));

        for (int k = L - 1; k >= 0; --k)

          sb.append(sb.charAt(k));

        int x = Integer.valueOf(sb.toString());

        if (x >= N && isPrime(x))

          return x;

      }

    }

    throw null;

  }

  public boolean isPrime(int N) {

    if (N < 2)

      return false;

    int R = (int) Math.sqrt(N);

    for (int d = 2; d <= R; ++d)

      if (N % d == 0)

        return false;

    return true;

  }

Our brute force works except when $N$ is 8 digits (as explained in Approach Framework when we established that all 8 digit palindromes are not prime), so we can skip all 8 digit numbers.

For each number, check whether it is a palindrome. If it is, check whether it is a prime. If the number is 8 digits, skip to the 9 digit numbers.

  public int primePalindrome(int N) {

    while (true) {

      if (N == reverse(N) && isPrime(N))

        return N;

      N++;

      if (10_000_000 < N && N < 100_000_000)

        N = 100_000_000;

    }

  }

  public boolean isPrime(int N) {

    if (N < 2)

      return false;

    int R = (int) Math.sqrt(N);

    for (int d = 2; d <= R; ++d)

      if (N % d == 0)

        return false;

    return true;

  }

  public int reverse(int N) {

    int ans = 0;

    while (N > 0) {

      ans = 10 * ans + (N % 10);

      N /= 10;

    }

    return ans;

  }

https://leetcode.com/problems/prime-palindrome/discuss/146798/Search-Palindrome-with-Even-Digits

All palindrome with even digits is multiple of 11.

We can prove as follow:

11 % 11 = 0
1111 % 11 = 0
111111 % 11 = 0
11111111 % 11 = 0

So:
1001 % 11 = (1111 - 11 * 10) % 11 = 0
100001 % 11 = (111111 - 1111 * 10) % 11 = 0
10000001 % 11 = (11111111 - 111111 * 10) % 11 = 0

For any palindrome with even digits:
abcddcba % 11
= (a * 10000001 + b * 100001 * 10 + c * 1001 * 100 + d * 11 * 1000) % 11
= 0

All palindrome with even digits is multiple of 11.
So among them, 11 is the only one prime
if (8 <= N <= 11) return 11
For other, we consider only palindrome with odd dights.

    public int primePalindrome(int N) {
        if (8 <= N && N <= 11) return 11;
        for (int x = 1; x < 100000; x++) {
            String s = Integer.toString(x), r = new StringBuilder(s).reverse().toString().substring(1);
            int y = Integer.parseInt(s + r);
            if (y >= N && isPrime(y)) return y;
        }
        return -1;
    }

    public Boolean isPrime(int x) {
        if (x < 2 || x % 2 == 0) return x == 2;
        for (int i = 3; i * i <= x; i += 2)
            if (x % i == 0) return false;
        return true;
    }

https://leetcode.com/problems/prime-palindrome/discuss/146888/Java-solution-building-closest-palindrome

Inspired by 564. Find the Closest Palindrome

    public int primePalindrome(int N) {
        while (N < Integer.MAX_VALUE) {
            N = nextPalin("" + N);
            if (isPrime(N)) {
                return N;
            }
            N++;
        }
        return -1;
    }
    private int nextPalin(String n) {
        int l = n.length();
        List<Integer> cands = new LinkedList<>();
        int half = Integer.valueOf(n.substring(0, (l + 1) / 2));
        for (int i = half; i <= half + 1; i++) {
            String halfString = "" + i;
            if (l % 2 == 1) {
                halfString = halfString.substring(0, halfString.length() - 1);
            }
            String newString = "" + i + new StringBuilder(halfString).reverse().toString();
            cands.add(Integer.valueOf(newString));
        }
        int ori = Integer.valueOf(n), result = Integer.MAX_VALUE;
        for (int cand : cands) {
            if (cand >= ori && cand < result) {
                result = cand;
            }
        }
        return result;
    }
    private boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        long l = (long)n;
        for (long i = 2; i * i <= l; i++) {
            if (l % i == 0) {
                return false;
            }
        }
        return true;
    }




https://leetcode.com/problems/prime-palindrome/discuss/146788/Getting-one-over-the-system-(O(1)-solution-in-Java)
generate an array of all the palindromic primes using 1553 ms. Next, I put them into my revenge array.