1

So I was practicing some algorithm problem and I ran into this problem.. When I type an input of over 800k, it will display a segment fault : 11. So the format for the input is :

    number of input
    input1
    input2
    ...

and the result should be the amount of number from 0 to 9 that's building the number from 1 till the input, for example if the input is 10 then there is 1 number 0, 2 number 1, 1 number 2, 1 number 3, 1 number 4, and so on till 9. Here is my code that's having the problem and it works just fine if I don't input anything beyond around 200k or something.

#include <stdio.h>
void coba(long long int arr[], long long int y)
{
  while(y)
  {
    arr[y%10]++;
    y/=10;
  }
}
void hitung(long long int arr[], long long int y,long long int limit)
{
  if(y>limit)
  {
    coba(arr, y);
    hitung(arr, y-1,limit);
  }
}
int main()
{
  int x,m;
  scanf("%d",&x);
  long long int a[x];
  long long int arr[x][10];
  for(int i = 0; i<x; i++)
  {
    scanf("%lld",&a[i]);
    for(int j = 0; j<10; j++)
    arr[i][j]=0;
  }
  for(int i = 0; i<x; i++)
  {
    m=1;
    printf("Case #%d: ",i+1);
    if(i)
    {
      for(int j = i-1; j>=0; j--)
      {
        if(a[i]>a[j])
        {
          hitung(arr[j], a[i], a[j]);
          for(int k = 0; k<9; k++)
          {
            arr[i][k]=arr[j][k];
            printf("%lld ",arr[i][k]);
          }
          arr[i][9]=arr[j][9];
          printf("%lld\n",arr[i][9]);
          m=0;
          break;
        }
      }
      if(m)
      {
        hitung(arr[i], a[i], 0);
        for(int k = 0; k<9; k++)
        {
          printf("%lld ",arr[i][k]);
        }
        printf("%lld\n",arr[i][9]);
      }
    }
    else
    {
      hitung(arr[i], a[i], 0);
      for(int k = 0; k<9; k++)
      {
        printf("%lld ",arr[i][k]);
      }
      printf("%lld\n",arr[i][9]);
    }
  }
}

And there is also a time limit to the question and that's why I'm using memoization here.

Calvin Alfredo
  • 33
  • 3
  • 2
    Not sure, but maybe you have out of bounds array indexes at some point. You can check that by adding some appropriate debug code. – Jabberwocky Nov 01 '19 at 16:06
  • On a Unix operating system such as Linux, a "segmentation violation" (also known as "signal 11", "SIGSEGV", "segmentation fault" or, abbreviated, "sig11" or "segfault") is a signal sent by the kernel to a process when the system has detected that the process was attempting to access a memory address that does not belong to it. Typically, this results in the offending process being terminated. https://support.microfocus.com/kb/doc.php?id=7001662 – Eduardo Fernandes Nov 01 '19 at 18:00
  • This is called *Stack Overflow*, pun both intended and not. – Antti Haapala -- Слава Україні Nov 01 '19 at 20:11

2 Answers2

0

Because hitung() is recursive, my bet is your large input leads to stack overflow. You can use a larger stack to solve this. Details are specific to your build environment.

donjuedo
  • 2,475
  • 18
  • 28
  • What do you mean by using a larger stack?? And how do I make it larger? – Calvin Alfredo Nov 02 '19 at 12:43
  • @CalvinAlfredo, Every time your program makes a function call, the parameters and return address are pushed onto the stack, which is memory with only so much space allocated. When the program uses too much, you get stack overflow, the name of this web site. You can allocate more space for the stack in a few ways, depending on how you build (compiler/linker, etc.) To make it larger, see this Q & A: https://stackoverflow.com/questions/2275550/change-stack-size-for-a-c-application-in-linux-during-compilation-with-gnu-com – donjuedo Nov 02 '19 at 13:37
0

I think long long int arr[x][10]; this is causing you the seg fault. If x>10^5 or 100k it becomes 100000*10*8 bytes or 8 giga bytes and your ram might fail to allocate this much space on the stack.

mghh
  • 47
  • 1
  • 6