Large array causing segmentation fault

Question

I wrote a code with the following specified constraints:

Hence I chose the data types for my variables accordingly. However my code fails all the test cases saying segmentation fault. (possibly because the array size they input is very large.) Is there a way to get more stack space or heap space? or get around this problem by declaring the array in some other way? Is there something else that's causing segmentation fault? Other people have solved this problem, so there must be a way.

this is the code:

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

long find_index(long x, long *cost, long n, long used_index)
{
    long i;
    for(i = 0; i < n; i++)
        if(*(cost + i) == x && i != used_index)
            return (i+1);
    return 0;
}

int purchase(long *cost, long n, long money)
{
    long i, index; 

    for(i = 0; i < n ;i++)
    {
        index = find_index((money - *(cost - i)),cost,n,i);
        if(index)
        {
           printf("%ld %ld\n",i+1,index);
           break;
        }   
    }
    free(cost);
    return 0;
}

int main(void)
{
    int t;
    long *cost, money, n, i;

    scanf("%d",&t);
    while(t > 0)
    {
        scanf("%ld",&money);

        scanf("%ld",&n);
        cost = (long *)malloc(n*sizeof(long));

        for(i = 0; i < n; i++)
            scanf("%ld",(cost+i));
        purchase(cost,n,money);
        t--;
    }

    return 0;
}

this is one of the hidden test cases they check for:

35 // this is t

299701136 // this is money

2044 // this is n

50293811 136626876 58515785 59281065 ..... goes on forever...

Add error checking please. Your program does not check the scanf result or the malloc result. If anything fails your entire program will explode. — Zan Lynx
Most people prefer array indexing: cost[-i] over pointer juggling: *(cost - i) , mostly because it is easier to read. — wildplasser
you aren't using stack space, malloc use heap space, if you want use stack space you have to declare an array variable instead malloc. — Carlos

jedzej jedzej · Accepted Answer · 2018-05-24T18:41:56

That's a lot of complex code to analyze, so instead of giving you a fish, I'll try to give you a rod.

Whatever platform, compiler and IDE you're using, there probably is a way to perform step-by-step debugging of your program at runtime. Maybe your assumptions are wrong and the allocation size is not causing this problem.

Learning basics of debugging is really great tool in programmer's hands. Here is an example tutorial video: https://www.youtube.com/watch?v=9gAjIQc4bPU

Large array causing segmentation fault

2 Answers