Last Updated: 15 Apr, 2021
Prime Palindrome
Moderate
Asked in company
Mr. Schodinger has locked all the cats of the universe in a giant box. You as an animal lover wanted to free all the cats but the box can be only opened with a password which is an integer. After researching Schrodinger you came to know that he loves prime numbers and palindrome numbers and his favourite number ‘N’. Now you know that the password is the smallest number that is greater than ‘N’ which is both prime and palindrome. Find that number and save the cats.
More formally, given an integer ‘N’, find the smallest integer ‘X’ such that:
1. ‘X’ >= ‘N’
2. ‘X’ is a prime number.
3. ‘X’ is a palindrome number.
Note:
An integer except ‘1’ is a prime number, if and only if its divisors are 1, and the number itself only. For example, 2, 3, 11 are prime numbers but 1, 4, 8 9 are not.
An integer is a palindrome number if the number remains the same after reversing all its digits. For example, 121, 1, 1331 are palindrome numbers but 12, 234234 are not.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains an integer ‘N’, representing the given integer.
Output Format:
For each test case, print one integer denoting the smallest number greater than the given number that is prime and palindrome.
The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10 ^ 8
Where ‘T’ is the total number of test cases, and ‘N’ is the given number.
Approaches
Approach: The idea is to iterate through integers starting from ‘N’ until we find a number that is both prime and palindrome. Here one key point is that we first check if the current number is palindrome or not, and if it is palindrome then only we check for prime because check palindrome of a number would take at most 8 operations as an integer can have at most 8 digits while checking for prime can be costly in terms of a number of operations.
Algorithm:
- Declare a variable say ‘CURRN’ and initialize it with ‘N’.
- Run an infinite while loop.
- If ‘CURRN’ is a palindrome number.
- If ‘CURRN’ is the prime number.
- Break the loop.
- If ‘CURRN’ is the prime number.
- Increase ‘CURRN’ by 1.
- If ‘CURRN’ is a palindrome number.
- Return ‘CURRN’.
Approach: A key observation here is that an even length palindrome except ‘11’ cannot be prime, as they all are divisible by ‘11’.
We can prove it by taking any arbitrary even digits palindrome lets take ‘abccba’, where ‘a’ , ‘b’, ‘c’ are some number from 0 to 9, of course ‘a’ can’t be ‘0’ here. Now ‘abccba’ can be written as (a * 100001 + b * 1001 * 10 + c * 11 + 100 ), which is divisible by 11.
For example, 22, 44, 1221, 1441,153351 etc. So in the above approach, we can avoid checking all numbers with even length. This method would greatly work when ‘N’ > 10 ^ 7, as now we do not need to check all 8 digits, and the first 9 digit palindrome prime is ‘100030001’.
Algorithm:
- Declare a variable say ‘CURRN’ and initialize it with ‘N’.
- If ‘N’ >= 10 ^ 7 and ‘N’ < 10 ^ 8
- Return 100030001.
- Run an infinite while loop.
- If ‘CURRN’ is a palindrome number.
- If ‘CURRN’ is the prime number.
- Break the loop.
- If ‘CURRN’ is the prime number.
- If ‘N’ > 11 and ‘CURRN’ have an even number of digits.
- Set ‘CURRN’ to the next odd digit number, i.e. ‘CURRN’ = 10 ^ (number of digits in ‘CURRN’ + 1).
- Else, increase ‘CURRN’ by 1.
- If ‘CURRN’ is a palindrome number.
- Return ‘CURRN’.
Approach: Instead of iterating over all numbers, we can just iterate over all palindromes. We can construct a palindrome by only the first half digits of the number for example, ‘1221’ can be constructed using ‘12’ and reverse of it i.e ‘21’. And we have already seen that any palindrome number with an even number of digits is divisible by ‘11’. So we now only generate palindromes with an odd number of digits and handle the case of ‘11’ separately.
Algorithm:
- If ‘N’ >= 8 and ‘N’ <= 11
- Return 11.
- Declare a variable say ‘START’ to store the first half digits of the starting number.
- Initialize the ‘START’ with 1.
- If the number of digits in ‘N’ is more than one.
- Declare a string say ‘STRN’ and set it with the string form of ‘N’.
- Declare a string ‘STRSTART’ to store the first half digits of ‘STRN’.
- Set ‘STRSTART’ = substring of ‘STRN’ starting from 0 to ‘STRN.length / 2’.
- Set ‘START’ to int of ‘STRSTART’.
- Run a loop from ‘i’ = ‘START’ to 100000
- Declare a string say ‘CURR’
- Declare a string say ‘REVERSE’ that stores reverse of ‘CURR’
- Join ‘CURR’ and substring of ‘REVERSE [1: length of ‘REVERSE’ ]’, this becomes a palindrome of odd ‘LENGTH’ and then converts it into an integer.
- If ‘CURR’ >= ‘N’ and ‘CURR’ is prime.
- Return ‘CURR’.