0

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?

Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
Lakshya Kejriwal
  • 1,340
  • 4
  • 17
  • 27
  • 1
    `scanf("%s" , &input);` --> `scanf("%s" , input);`. `input` is already an array. – mch Jun 30 '15 at 10:43
  • 2
    Please run in a debugger to catch the crash as it happens, if you can't solve it even when you know where it happens then at least tell *us* where that is, and please edit your question to only include the relevant parts. – Some programmer dude Jun 30 '15 at 10:43
  • 3
    are you sure you want these big arrays on stack? Also, you should initialize it with `0` rather than `NULL`. – Sourav Ghosh Jun 30 '15 at 10:43
  • 2
    @mch As `input` is an array, it will work anyway. – Some programmer dude Jun 30 '15 at 10:44
  • 1
    Regarding the comment by @SouravGhosh, the stack on most systems is limited to single digit amount of megabytes. The default on Linux is 8MB, but may be lower. Your arrays alone use over 3MB. – Some programmer dude Jun 30 '15 at 10:45
  • @Pileborg I have run it in a debugger mode but I was unable to catch any error for the various test cases. Only when I submit my solution I get a runtime error(SIGSEGV) – Lakshya Kejriwal Jun 30 '15 at 10:50
  • Yes but how do you know the stack size being used by SPOJ? The linked question contains a warning: *"Warning: large Input/Output data, be careful with certain languages"*. Your function `find_palin` with those massive arrays is recursively calling itself. – Weather Vane Jun 30 '15 at 11:03
  • Have you tested your code with the million digit number required? – Weather Vane Jun 30 '15 at 11:06
  • @Vane The memory limit is restricted to 1536MB by spoj – Lakshya Kejriwal Jun 30 '15 at 11:08
  • How much of that 1536MB will be allocated to the stack? – Weather Vane Jun 30 '15 at 11:16
  • @Vane It has not been mentioned but still there will be only one recursive call per test case – Lakshya Kejriwal Jun 30 '15 at 11:27
  • Enable your compiler warnings. My compilation gives "warning C4715: 'find_palin' : not all control paths return a value". The program crashes when I enter `1` then `9`. – Weather Vane Jun 30 '15 at 11:43
  • @Vane I'm getting the correct answer for 9 i.e. 11. My compiler warnings are on and I get no such warning – Lakshya Kejriwal Jun 30 '15 at 11:50
  • When I reduce the array sizes your examples now work, so I advise you to pay heed to the comments before mine and not brush them off. With one recursive call per test case you have approx 6MB on the stack. – Weather Vane Jun 30 '15 at 12:02
  • @Vane The problem requires that the input be 1000000 long. So how can I go about reducing the array sizes and solve the problem? – Lakshya Kejriwal Jun 30 '15 at 12:17
  • Allocate several MB on the _stack_ combined with recursion... You need to step back from this code and study the basics of computers and computer programs. And avoid recursion in general. – Lundin Jun 30 '15 at 12:39

1 Answers1

0

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;
}
Community
  • 1
  • 1
Weather Vane
  • 33,872
  • 7
  • 36
  • 56
  • Thanks a lot. I'm not getting the segmentation error. But for some reason I'm getting a wrong answer for this.Any suggestions? – Lakshya Kejriwal Jun 30 '15 at 13:28
  • Now that I have answered your asked question, I hope you will "accept" this answer, not pile on the different unspecific question "why isn't my program working?" – Weather Vane Jun 30 '15 at 13:50
  • Thanks. The input `10000001` does not conclude after some time. The input `1000000000001` concludes fairly quickly but doesn't print any output, because it runs out of memory. I haven't an idea as to why, but the recursion was called 813 times! As opposed to 2 when it works correctly, as you commented. – Weather Vane Jun 30 '15 at 14:11
  • The input `10001` gives the incorrect answer `11011` after 11 recursive calls. The correct answer is `10101`. – Weather Vane Jun 30 '15 at 14:25
  • My last-but-one comment was in error. The input `10000001` gives the incorrect result `11111111` after 112 recursions. – Weather Vane Jun 30 '15 at 16:23