PROJECT EULER SOLUTION # 55

Solution to problem number 55 of Project Euler.

Question # 55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?

Solution # 55

/***************************************************************************************/

#include<stdio.h>

#include<time.h>

#include<conio.h>

#include<stdlib.h>

int isPalindrome(int*,int);

int*reverseArray(int*,int);

int*sumArray(int*,int*,int);

int*toArray(long);

int countDigits(long);

int isLychrel(long);

void main()

{

      

       int i,counter=0;

       for(i=2;i<10000;i++)

       {

              if(isLychrel(i))

              {

                     counter++;

                     //printf("%d\n",i);

              }

       }

       printf("\ncounter = %d\n",counter);

       printf("EXECUTION TIME = %f",clock()/(float)CLK_TCK);

       system("pause");

}

int isLychrel(long n)

{

       int counter=0,digits,i;

       int*arr,*rarr,*sum;

       digits=countDigits(n);

       arr=toArray(n);

       while(counter<=50)

       {

              counter++;

              rarr=reverseArray(arr,digits);

              sum=sumArray(arr,rarr,digits);

              if(sum[0]==0)

              {

                     for(i=0;i<digits;i++)

                           sum[i]=sum[i+1];

              }

              else

                     digits++;

              if(isPalindrome(sum,digits))

                     return 0;

              arr=sum;

              //arr=assignArray(sum,digits);

       }

       return 1;

}

int isPalindrome(int *arr,int len)

{

       int i,j;

       for(i=0,j=len-1;i<len;i++,j--)

       {

              if(arr[i]!=arr[j])

                     return 0;

       }

       return 1;

}

int*reverseArray(int*arr,int len)

{

       int*rarr,i,j;

       rarr=(int*)malloc(sizeof(int)*len);

       for(i=len-1,j=0;i>=0;i--,j++)

              rarr[j]=arr[i];

       return rarr;

}

int *sumArray(int*a,int*b,int len)

{

       int*sum,i;

       sum=(int*)malloc(sizeof(int)*(len+1));

       for(i=0;i<len+1;i++)

              sum[i]=0;

       for(i=len-1;i>=0;i--)

       {

              sum[i+1]+=a[i]+b[i];

              if(sum[i+1]>9)

              {

                     sum[i+1]=sum[i+1]%10;

                     sum[i]+=1;

              }

       }

       return sum;

}

int countDigits(long n)

{

       int counter=0;

       while(n)

       {

              counter++;

              n/=10;

       }

       return counter;

}

int *toArray(long n)

{

       int *arr,len,i;

       len=countDigits(n);

       arr=(int*)malloc(sizeof(int)*len);

       for(i=len-1;i>=0;i--)

       {

              arr[i]=n%10;

              n/=10;

       }

       /*

       for(i=0;i<len;i++)

              printf("%d",arr[i]);

              */

       return arr;

}

/***************************************************************************************/