Problem 4: Largest palindrome number

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


Sol.
The problem can be solved easily by brute force i.e. checking all the products of 3-digit numbers to be palindrome and then determining the largest among them.
The code for palindrome checking is easy, we can simply reverse the number and check the equality.
int ispalindrome(int n)
{
        int temp=n,rem,sum;
        while(n>0)
        {
              rem=n%10;
              n=n/10;
              sum=sum*10 + rem;
         }
         if(sum==temp)
              return 1;
         else
              return 0;
}


int main()
{
      int big=0;
      for(i=999;i>=100;i--)
          for(i=999;i>=100;i--)
              if(ispalindrome(i*j)&&(big<(i*j)))
                         big=(i*j);
}
As you may have noticed, it takes too much time. So, I used some of my observations regarding the problem to reduce the time.


1. A palindrome number with even number of digits is always divisible by 11. So, at least  one of the numbers must be divisible by 11.Thus the inner loop can be decreased to be decremented by 11 each time.
2.There are many redundant multiplications like 999*998 and then 998*999.That must be reduced.For that we can find the nearest number to 'i' which is divisible by 11 and is less than 'i'.
It can be done easily as the number would be : i-(i%11)
3. The last digit of the palindrome number can't be zero as the first isn't. So, all the numbers which are multiple of 10 can be eliminated from the consideration.


The improved code can be:
int main()
{
         int big=0,i,j;
         for(i=999;i>=101;i--)
         {
                   if(i%10==0)
                          continue;
                   x=i-(i%11);
                   for(j=x;j>=121;j-=11)
                   {
                            n=i*j;
                            if(ispalindrome(n)&& big < n)
                                   big=n;
                   }
          }
          printf("%d",big);
}


Please post your comments and doubts...
Suggestion for better algorithms are always welcome.....
This is me signing off for today....