I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everything gonna be alright ;-). My first approach was to find all the prime numbers in range 1...100,000,000 and check whether each of them is a palindrome or not? then push all the prime palindromes in an array and for input binary search for the first and last palindrome number. But soon I noticed that I can approach the problem from another aspect, produce all palindromes and check whether they are prime or not? So I had to have an idea about the number of palindromes less than 100,000,000, I started counting them.
1 digit (preferably prime) palindromes --> 2 - 3 - 5 - 7 - 9 => 5 numbers
2 digit (preferably prime) palindromes --> 5 numbers.
3 digit (preferably prime) palindromes --> 50 numbers
4 digit (preferably prime) palindromes --> 50 numbers
5 digit (preferably prime) palindromes --> 500 numbers
6 digit (preferably prime) palindromes --> 500 numbers
....
I counted them using rule of product (multiplication principle).
They are not too many to check, I check each of them to see whether it is a prime or not, if yes I push them in an array. But the problem is how do we check an 8 digit palindrome to see whether it is a prime or not?
To see a number n is prime or not, you have to check all the prime numbers less than sqrt(n), if n is divisible by a prime number less than sqrt(n), then it is not prime, otherwise it is a prime. So at first I find all the prime numbers from 1...10000, which 10000 = sqrt(100,000,000). You can find these prime numbers using sieve of eratosthenes or just by checking each number to see it is prime or not. That's how I solved the problem:-).
To see a number n is prime or not, you have to check all the prime numbers less than sqrt(n), if n is divisible by a prime number less than sqrt(n), then it is not prime, otherwise it is a prime. So at first I find all the prime numbers from 1...10000, which 10000 = sqrt(100,000,000). You can find these prime numbers using sieve of eratosthenes or just by checking each number to see it is prime or not. That's how I solved the problem:-).
How is the product rule applicable to palindromes
ReplyDeleteI used "product rule" to count the number of palindromes,
ReplyDeleteLet's say you want to count the number of 5 digit palindromes,
_ _ _ _ _
So we have 5 slots, and pay attention that we want to count "preferably prime palindromes", So we can't put "even digits" at the first slot, so only 1, 3, 5, 7, 9, the first digit has 5 options, the second digit but has all the 10 options and the third has all the 10 options, so there are 5 x 10 x 10 = 500 options that maybe they are palindromes.