Array Overflow Prevention

[Tarique]

/**
A palindrome is a number that is the same whether it is read from
left-to-right or right-to-left. For example, 121 and 34543 are both
palindromes. It turns out that nearly every integer can be transformed
into a palindrome by reversing its digits and adding it to the original
number. If that does not create a palindrome, add the reverse of the new
number to itself. A palindrome is created by repeating the process of
reversing the number and adding it to itself until the number is a
palindrome.Create the method palindrome, which takes a number N
that is to be transformed and returns a number that is the resultant
palindrome from this process.Of course if N is already a palindrome,
return it without changing it.Though it is theorized that all numbers
can be transformed to palindromes in this way,some numbers do not
converge in a reasonable amount of time.

**For instance, 196 has been carried out to 26,000 digits without
finding a palindrome.
So if the method finds that the resultant palindrome must be greater
than 1,000,000,000,return the special value -1 instead.
**

DEFINITION
Method: palindrome
Parameters: int
Returns: int
Method signature (be sure your method is public): int palindrome(int N);

NOTES
- Leading zeroes are never considered part of a number when it is
reversed. For instance, 12's reverse will always be 21 regardless of
whether it is represented as 12, 012, or 0012. Examples with leading
zeroes use the leading zeroes for clarity only.

EXAMPLES
Worked examples:
Example 1: N = 28
28 + 82 = 110
110 + 011 = 121, a palindrome. Return 121

Example 2: N = 51
51 + 15 = 66, a palindrome. Return 66

Further examples:
Example 3: N = 11, return 11
Example 4: N = 607, return 4444
Example 5: N = 196, return -1
**/

__________________________________________________ _________________________

My question is how do i check if the resultant palindrome is greater
than 1,000,000,000 ?My code uses an array to store the digits of the
sum,n i cannot have an array that darn long.

Please suggest some ideas.Also let me know if there are any other bugs.

PS: the code will crash with the inputs 196 and 197 as well.However
apart from these non-converging numbers i do obtain the correct result.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MAX 10000000UL
#define ARR 50000UL
int check_if_palindrome(int *str,int length)
{
int *back = str + length - 1;
while(str <= back)
{
if(*str++ != *back--)
return 0;
}
return 1;
}

int palindrome(int num)
{
int digit=0,rev_num=0,sum=0;
int store_num=num,store_sum=0;
int i=0,n=1,k=0;
int hold[ARR];

while(num/10!=0)
{
digit=num%10;
hold[i++]=digit;
num=num/10;
}
hold[i++]=num;
hold[i]='\0';
if(check_if_palindrome(hold,i))
return store_num;
for(k=0;k<i;k++)
rev_num+=(hold[k]*((int)pow(10,i-k-1)));
sum=store_num+rev_num;
memset(hold,0,ARR);
i=0;store_sum=sum;

while(sum/10!=0)
{
digit=sum%10;
hold[i++]=digit;
sum=sum/10;
}
hold[i++]=sum;
hold[i]='\0';

if(check_if_palindrome(hold,i))
return store_sum;
else
palindrome(store_sum);
}

int main(void)
{
int num,test=0,ch;
printf("Enter the integer");
test=scanf_s("%d",&num);
while(test!=1)
{
while (('\n' != (ch = getchar())) && (EOF != ch));
puts("Enter an integer value");
test=scanf_s("%d",&num);
}
printf("The palindrome is%d",palindrome(num));
return 0;
}

[David Marsh]

Tarique wrote:

/**
A palindrome is a number that is the same whether it is read from
left-to-right or right-to-left. For example, 121 and 34543 are both
palindromes. It turns out that nearly every integer can be transformed
into a palindrome by reversing its digits and adding it to the original
number. If that does not create a palindrome, add the reverse of the new
number to itself. A palindrome is created by repeating the process of
reversing the number and adding it to itself until the number is a
palindrome.Create the method palindrome, which takes a number N
that is to be transformed and returns a number that is the resultant
palindrome from this process.Of course if N is already a palindrome,
return it without changing it.Though it is theorized that all numbers
can be transformed to palindromes in this way,some numbers do not
converge in a reasonable amount of time.

**For instance, 196 has been carried out to 26,000 digits without
finding a palindrome.

196 is the smallest number that doesn't form a palindrome in this
manner. As the numbers get bigger, fewer form palindromes.

My question is how do i check if the resultant palindrome is greater
than 1,000,000,000 ?My code uses an array to store the digits of the
sum,n i cannot have an array that darn long.

Use a non-standard extended precision arithmetic library (e.g.
MIRACL) or write your own bignum code for addition; it's not too
difficult.

>
Please suggest some ideas.Also let me know if there are any other bugs.

Check out this link: http://www.jasondoucette.com/worldrecords.html

Also, see: Scientific American, April 1984, Computer Recreations

David

[Tarique]

Tarique wrote:

....snip..

PS: the code will crash with the inputs 196 and 197 as well.However
apart from these non-converging numbers i do obtain the correct result.

.....snip...

Ive just modified the code a bit n it still crashes with the input 89 (A
Stack overflow occurs..i'm using visual studio 2005)although it takes
care of 196 n 197 for which it used to crash earlier.
I tried tracing it but could not figure out the reason.Can anyone help
me out?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define ARR 50000UL
int check_if_palindrome(int *str,int length)
{
int *back = str + length - 1;
while(str <= back)
{
if(*str++ != *back--)
return 0;
}
return 1;
}
int palindrome(int num)
{
int digit=0,rev_num=0,sum=0;
int store_num=num,store_sum=0;
int i=0,k=0;
int hold[ARR];

while(num/10!=0)
{
digit=num%10;
hold[i++]=digit;
num=num/10;
}
hold[i++]=num;
hold[i]='\0';

if(check_if_palindrome(hold,i))
return store_num;
for(k=0;k<i;k++)
rev_num+=(hold[k]*((int)pow(10,i-k-1)));
sum=store_num+rev_num;
if(sum>50000)return -1;
memset(hold,0,ARR);
i=0;store_sum=sum;

while(sum/10!=0)
{
digit=sum%10;
hold[i++]=digit;
sum=sum/10;
}
hold[i++]=sum;
hold[i]='\0';
if(check_if_palindrome(hold,i))
return store_sum;
else
palindrome(store_sum);
}

int main(void)
{
int num,test=0,ch;
printf("Enter the integer");
test=scanf_s("%d",&num);
while((test!=1)|| (num<=1)||(num>=10000))
{
while (('\n' != (ch = getchar())) && (EOF != ch));
puts("Enter an integer value within 1 and 10000 inclusive");
test=scanf_s("%d",&num);
}
if(palindrome(num)==-1)
printf("Sorry the number does not converge within the given range\n");
else
printf("The palindrome is%d\n",palindrome(num));
return 0;
}

[Ben Bacarisse]

Tarique <ta*****@invalid.comwrites:

Tarique wrote:

...snip..

>PS: the code will crash with the inputs 196 and 197 as well.However
apart from these non-converging numbers i do obtain the correct
result.

....snip...

Ive just modified the code a bit n it still crashes with the input 89
(A Stack overflow occurs..i'm using visual studio 2005)although it
takes care of 196 n 197 for which it used to crash earlier.
I tried tracing it but could not figure out the reason.Can anyone help
me out?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define ARR 50000UL
int check_if_palindrome(int *str,int length)
{
int *back = str + length - 1;
while(str <= back)
{
if(*str++ != *back--)
return 0;
}
return 1;
}
int palindrome(int num)
{
int digit=0,rev_num=0,sum=0;
int store_num=num,store_sum=0;
int i=0,k=0;
int hold[ARR];

50,000 ints in automatic storage (on your system "on the stack").

while(num/10!=0)
{
digit=num%10;
hold[i++]=digit;
num=num/10;
}
hold[i++]=num;
hold[i]='\0';

if(check_if_palindrome(hold,i))
return store_num;
for(k=0;k<i;k++)
rev_num+=(hold[k]*((int)pow(10,i-k-1)));
sum=store_num+rev_num;

This is not the main point, but if you calculate the result of the
reverse (and the sum) as an int, what is the point of using an array
for the digits? If you are prepared to limit the search to those that
produce intermediate results that fit into an integer variable, there
is not need for the array. If you need the array to represent very
large intermediate values (quite likely) then you can't use the above
to calculate the reverse and the sum.

if(sum>50000)return -1;
memset(hold,0,ARR);
i=0;store_sum=sum;

while(sum/10!=0)
{
digit=sum%10;
hold[i++]=digit;
sum=sum/10;
}
hold[i++]=sum;
hold[i]='\0';
if(check_if_palindrome(hold,i))
return store_sum;
else
palindrome(store_sum);

A recursive call that will require a fresh 50,000 int array. Some
numbers will require dozens of recursive calls. This is very likely
to be a problem.

}

PS. Use more white space and copy one of the common indentation
styles used for C.

--
Ben.

[David Marsh]

Tarique wrote:

Tarique wrote:

...snip..

>PS: the code will crash with the inputs 196 and 197 as well.However
apart from these non-converging numbers i do obtain the correct result.

....snip...

Ive just modified the code a bit n it still crashes with the input 89 (A
Stack overflow occurs..i'm using visual studio 2005)although it takes
care of 196 n 197 for which it used to crash earlier.
I tried tracing it but could not figure out the reason.Can anyone help
me out?

If you are restricting your program to numbers that fit into an
int, it doesn't make sense to use an array to hold the digits.
For numbers too large to fit into native data types you could use
arrays of chars that simulate numbers, each element holding one
digit, then write code that "adds" these arrays by adding
corresponding elements, implementing carrys if necessary. Also,
you should be able to set some limit for the number of
reversals/adds for the cases where the starting numbers do not
form palindromes.

I wrote a reverse/add palindrome program that uses this approach.
The size of the numbers is limited only by the amount of
available memory. It's too long to post here but if you would
like to post a working email address I'll send it to you.

David