Largest Palindrome

Problem :

The largest palindrome number made from the product of two 2-digit numbers is 9009 = 91 × 99. 

Find the largest palindrome made from the product of two 3-digit numbers.

Answer :906609

This Is  very easy ProjectEuler Problem. but it worth trying. First of all Try it by yourself then back to us even if you succeed because getting answer should not be our only objective. How efficient is our approach also matters.

First Approach People try is find largest palindrome in range 100*100 to 999*999 this is a very obvious but wrong approach because all numbers in this range are not multiple of 2 3 digit number .

Try this Python Code to check it out

1. #Python 2.7
2. #beginner to computer Science
3. limit=999*999
4. base=100
5. def ispalindrom(n):
6.     st=str(n)
7.     if(st==st[::-1]):
8.         return True
9.     else:
10.         return False
11. for i in range(limit,base,-1):
12.     if ispalindrom(i):
13.         print i
14.         break

\
Now try Another approach :> Check all number that is multiple of  two 3 digit number. and find largest palindrome number among them.
It will give correct result but at what cost
We know multiplication is very costly in computation & this approach takes about =806907  multiplication of two three digit number
Check it out by yourself

1. //C-Program
2. //Very costly with respect to calculation required
3. #include<stdio.h>
4. #include<string.h>
6. int isPalindrome_num(long long int n){
7.         /*
8.           ****<string.h>
9.            Used to check number is palindrome or not
10.            """
11.              isPalindrome_num(n)
12.              return 1 if palindrome
13.              return 0 if not palindrome
14.            """
15.         */
16.         char a[30];
17.         char b[30];
18.         sprintf(a,"%d",n); //convert number in string & store it in array a
19.         strcpy(b,a); //copy b<-a
20.         _strrev(b);  //reverse b
21.         if(strcmp(a,b)==0) //compare
22.             return 1;
23.         else
24.             return 0;
25. }
26. 
    
27. int main(){
28.         int i,j,p,count=0,t1,t2;
29.         int max=10001; //least 4 digit number
30.         for(i=999;i>100;i--){
31.                 for(j=999;j>100;j--){
32.                         p=i*j;
33.                         count++;
34.                         //printf("%d, ",p);
35.                         if(p>max && isPalindrome_num(p)==1){
36.                                 max=p;
37.                                 t1=i;
38.                                 t2=j;
39.                                 break;
40.                         }
41.                 }
42.         }
43.         printf("largest required palindrome =%d * %d = %d",t1,t2,max);
44.         printf("\nnumber of multplication required = %d",count);
45.         return 0;
46. }

YOu Can See number of multiplication required 

But We can Very effectively reduced number of multiplication required by eliminatic case.we don't need to check .
let we find an palindrome X then reduce all possible multiplication which produce result less than X 
Then you can see how efficient your code become .
Check it Out.

1. //C-Program
2. //Optimize number of multiplication required 
3. #include<stdio.h>
4. #include<string.h>
6. int isPalindrome_num(long long int n){
7.         /*
8.           ****<string.h>
9.            Used to check number is palindrome or not
10.            """
11.              isPalindrome_num(n)
12.              return 1 if palindrome
13.              return 0 if not palindrome
14.            """
15.         */
16.         char a[30];
17.         char b[30];
18.         sprintf(a,"%d",n); //convert number in string & store it in array a
19.         strcpy(b,a); //copy b<-a
20.         _strrev(b);  //reverse b
21.         if(strcmp(a,b)==0) //compare
22.             return 1;
23.         else
24.             return 0;
25. }
28. int main(){
29.         int i,j,p,count=0,t1,t2;
30.         int max=10001; //least 4 digit number
31.         for(i=999;i>100;i--){
32.                 for(j=999;j>100;j--){
33.                         p=i*j;
34.                         count++;
35.                         if(p<max) //stop mult when p<max it is worthless as we want largest
36.                             break;
37.                         else
38.                             if(isPalindrome_num(p)==1){ //if p>max & it is a palindrom
39.                                     max=p; //update max
40.                                     t1=i;  //just for printing result
41.                                     t2=j;
42.                                     break;
43.                                }
44.                 }
45.         }
46.         printf("largest required palindrome =%d * %d = %d",t1,t2,max);
47.         printf("\nnumber of multplication required = %d",count);
48.         return 0;
49. }

Optimize code >largest palindrome 

You can see slight Modification reduce number of multiplication by about 88 times :)

Please Suggest If you found Any Bug or you know better approach to solve it .
Thank You