I'm trying to solve the Next Palindrome problem on SPOJ. Here is the link to the problem SPOJ
This is my code for the problem. I get correct results when I run it on my machine for the following test cases :
9 11
99 101
808 818
This is my code :
#include<stdio.h>
#include<string.h>
char k[1000004];
int find_palin(char num[])
{
int len = strlen(num);
char str1[1000004] = {NULL};
char str3[500002] = {NULL};
char str2[500002] = {NULL};
char rev[500002] ={NULL};
if(len%2==0)
{
int half = (len)/2;
int i;
int j=0;
for(i=1;i<=len-1;++i)
{
if(num[i]!='0')
break;
k[i]='0';
}
if(i>len-1)
{
k[0]=num[0];
k[len-1]=num[0];
return 0;
}
for(i=0;i<half;++i)
str1[i] = num[i];
for(i=half;i<len;++i)
str3[j++] = num[i];
for(i=0 , j=half-1;i<half;++i,--j)
{
if(str3[i]>=str1[j])
break;
else
rev[i]=str1[j];
}
if(i>=half)
{
strcat(str1,rev);
for(i=0;i<len;++i)
k[i]=str1[i];
return 0;
}
else
{
for(i=0;i<half;++i)
str3[i] = '0';
if(str1[half-1]!='9')
str1[half-1]++;
else
{
for(i=half-1;i>=0;--i)
{
if(str1[i]=='9')
str1[i] = '0';
else
{
str1[i]++;
break;
}
}
if(i<0)
{
str1[half]='0';
str1[0] = '1';
}
}
strcat(str1,str3);
find_palin(str1);
}
}
else
{
int half = (len-1)/2;
int i;
int j=0;
if(len==1)
{
if(num[0]=='9')
{
k[0] = '1';
k[1] = '1';
return 0;
}
k[0] = ++num[0];
return 0;
}
for(i=1;i<=len-1;++i)
{
if(num[i]!='0')
break;
k[i]='0';
}
if(i>len-1)
{
k[0]=num[0];
k[len-1]=num[0];
return 0;
}
for(i=0;i<half;++i)
str1[i] = num[i];
for(i=half+1;i<len;++i)
str3[j++] = num[i];
str2[0] = num[half];
for(i=0 , j=half-1;i<half;++i,--j)
{
if(str3[i]>=str1[j])
break;
else
rev[i]=str1[j];
}
if(i>=half)
{
strcat(str2 , rev);
strcat(str1 , str2);
for(i=0;i<len;++i)
k[i]=str1[i];
return 0;
}
else
{
for(i=0;i<half;++i)
str3[i] = '0';
if(str2[0]!='9')
{
str2[0]++;
strcat(str2,str3);
strcat(str1,str2);
find_palin(str1);
}
else
{
str2[0] = '0';
if(str1[half-1]!='9')
str1[half-1]++;
else
{
for(i=half-1;i>=0;--i)
{
if(str1[i]=='9')
str1[i] = '0';
else
{
str1[i]++;
break;
}
}
if(i<0)
{
str1[half]='0';
str1[0] = '1';
}
}
strcat(str2,str3);
strcat(str1,str2);
find_palin(str1);
}
}
}
}
int main()
{
char input[1000004];
int t;
scanf("%d" , &t);
int i;
for(i=0;i<t;++i)
{
scanf("%s" , &input);
find_palin(input);
printf("%s\n" , k);
}
return 0;
}
When I try to submit the code it gives Segmentation Fault. Can someone please help me as to why I'm getting this error?
The way to use large arrays is to allocate memory on the heap not on the stack. I have done this in your program to show you. Instead of doing that in main I lazily moved input[] to be a global var. You can't do that in find_palin because of the recursion, and anyway global variables are frowned on.
I also changed all your return 0 statements to goto so that a common clean-up can be done. It is not elegant, but I didn't want to change the structure of your code.
I also tweaked a few other things, such as checking the input was valid, and using a single #define from which all other sizes specified are derived.
#include<stdio.h>
#include<string.h>
#define ARRSIZE 1000004 // don't hard code stuff
char k[ARRSIZE];
char input[ARRSIZE]; // move out of main
void find_palin(char num[]) // change return type to void
{
int len = strlen(num);
char *str1 = calloc(ARRSIZE, sizeof(*str1)); // allocate and zero
char *str2 = calloc(ARRSIZE/2, sizeof(*str2));
char *str3 = calloc(ARRSIZE/2, sizeof(*str3));
char *rev = calloc(ARRSIZE/2, sizeof(*rev));
if (str1 == NULL || str2 == NULL || str3 == NULL || rev == NULL)
exit (1); // check memory allocations
if(len%2==0)
{
int half = (len)/2;
int i;
int j=0;
for(i=1;i<=len-1;++i)
{
if(num[i]!='0')
break;
k[i]='0';
}
if(i>len-1)
{
k[0]=num[0];
k[len-1]=num[0];
goto endfunc; // replace all return statements
}
for(i=0;i<half;++i)
str1[i] = num[i];
for(i=half;i<len;++i)
str3[j++] = num[i];
for(i=0 , j=half-1;i<half;++i,--j)
{
if(str3[i]>=str1[j])
break;
else
rev[i]=str1[j];
}
if(i>=half)
{
strcat(str1,rev);
for(i=0;i<len;++i)
k[i]=str1[i];
goto endfunc;
}
else
{
for(i=0;i<half;++i)
str3[i] = '0';
if(str1[half-1]!='9')
str1[half-1]++;
else
{
for(i=half-1;i>=0;--i)
{
if(str1[i]=='9')
str1[i] = '0';
else
{
str1[i]++;
break;
}
}
if(i<0)
{
str1[half]='0';
str1[0] = '1';
}
}
strcat(str1,str3);
find_palin(str1);
}
}
else
{
int half = (len-1)/2;
int i;
int j=0;
if(len==1)
{
if(num[0]=='9')
{
k[0] = '1';
k[1] = '1';
goto endfunc;
}
k[0] = ++num[0];
goto endfunc;
}
for(i=1;i<=len-1;++i)
{
if(num[i]!='0')
break;
k[i]='0';
}
if(i>len-1)
{
k[0]=num[0];
k[len-1]=num[0];
goto endfunc;
}
for(i=0;i<half;++i)
str1[i] = num[i];
for(i=half+1;i<len;++i)
str3[j++] = num[i];
str2[0] = num[half];
for(i=0 , j=half-1;i<half;++i,--j)
{
if(str3[i]>=str1[j])
break;
else
rev[i]=str1[j];
}
if(i>=half)
{
strcat(str2 , rev);
strcat(str1 , str2);
for(i=0;i<len;++i)
k[i]=str1[i];
goto endfunc;
}
else
{
for(i=0;i<half;++i)
str3[i] = '0';
if(str2[0]!='9')
{
str2[0]++;
strcat(str2,str3);
strcat(str1,str2);
find_palin(str1);
}
else
{
str2[0] = '0';
if(str1[half-1]!='9')
str1[half-1]++;
else
{
for(i=half-1;i>=0;--i)
{
if(str1[i]=='9')
str1[i] = '0';
else
{
str1[i]++;
break;
}
}
if(i<0)
{
str1[half]='0';
str1[0] = '1';
}
}
strcat(str2,str3);
strcat(str1,str2);
find_palin(str1);
}
}
}
endfunc: // free the memory
free(rev);
free(str3);
free(str2);
free(str1);
}
int main()
{
int t;
int i;
if (1 != scanf("%d" , &t)) // check garbage input
exit (1);
for(i=0;i<t;++i)
{
if (1 != scanf("%s" , input)) // remove &
exit (1); // check garbage input
find_palin(input);
printf("%s\n" , k);
}
return 0;
}