Prime Palindrome

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
0 upvote
Asked in company
Snapdeal Ltd.

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
3
9

Sample Output 1:

3
11

Explanation For Sample Input 1:

Test case 1:
3 is the smallest number greater than or equal to the given number that is both prime and palindrome.

Test case 2:
‘11’ is the smallest number greater than or equal to the given number i.e 9, which is both prime and palindrome.

Sample Input 2:

1
112

Sample Output 2:

131

Explanation For Sample Input 2:

Test case 1:
‘131’ is the smallest number greater than or equal to the given number i.e 112, which is both prime and palindrome.
Hint

Can you check all numbers by running a loop?

Approaches (3)
Brute Approach

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:

 

  1. Declare a variable say ‘CURRN’ and initialize it with ‘N’.
  2. Run an infinite while loop.
    • If ‘CURRN’ is a palindrome number.
      • If ‘CURRN’ is the prime number.
        • Break the loop.
    • Increase ‘CURRN’ by 1.
  3. Return ‘CURRN’.
Time Complexity

O(N), where ‘N’ is the given number.

 

Although we cannot prove how many iterations will be performed for a given number ‘N’, but Taking the upper bound of iteration we can find the palindrome prime number in ‘N’ iterations, Checking an integer for prime number ‘X’ takes O (sqrt(X)) time but there will be at most sqrt(N) number that are a palindrome. Hence the overall time complexity will be O(N) + O(sqrt(N) * sqrt(N)) = O(N).

Space Complexity

O(1)

 

As we are not using any extra space.

Code Solution
(100% EXP penalty)
Prime Palindrome
Full screen
Console