how to store upto 1,000,000,000 elements

Question

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

int max_b(int,int);
int max(int[],int);

int main(){

    int num_tests;
    scanf("%d",&num_tests);
    int array_n[num_tests];
    int array_b[num_tests];
    int i,j;
    for (i=0;i<num_tests;i++){
        scanf("%d %d",&array_n[i],&array_b[i]);
    }
    for (j=0;j<num_tests;j++){
        int A = 1;
        int N = array_n[j];
        int B = array_b[j];
        int max_num_b;
        max_num_b = max_b(N,B);
        int array2[max_num_b];
        int k;
        for (k=0;k<max_num_b;k++){
            int num_a,num_b;
            num_a = N-(k+1)*B;
            num_b = k+1;
            array2[k] = num_a*num_b;            
        }
        printf("%d\n",max(array2,max_num_b));
    }

}

int max(int array[],int a){
    int max_num = 0,i;
    for (i=0;i<a;i++){
        if (array[i] > max_num){
            max_num = array[i];
        }
    }
    return max_num;
}

int max_b(int n,int b){
    return n/b;
}

my first input is num of test cases T (say 1),and second input is 1,000,000,000 1 . So then the code tries to form an array of 10^9 size and the program ends up showing segmentation fault. However the code runs well upto 1,000,000 1. how can I store upto 10^9 elements. If its not possible then how can I store so many numbers. Should I use malloc, if yes then how. any help would be appreciated.

Answer 1

You should NOT use variable length array declarations when the size is determined at runtime.

I would suggest you use malloc() instead. Replace the following lines

int num_tests;
scanf("%d",&num_tests);
int array_n[num_tests];
int array_b[num_tests];

With

int num_tests, *array_n, *array_b;

scanf("%d", &num_tests);

array_n = malloc(num_tests * sizeof(int));
if (array_n == NULL)
{
    printf("Memory allocation error for array_n!\n");
    return -1;
}

array_b = malloc(num_tests * sizeof(int));
if (array_b == NULL)
{
    /* cleanup */
    free(array_n);

    printf("Memory allocation error for array_b!\n");
    return -1;
}

As other comments pointed out, 1,000,000,000 elements need roughly 4GB of memory (double that as you have two arrays). So, you may run out of memory allocating this many integers.

Answer 2

For a billion ints in two arrays, you will need nearly 8GiB of storage, assuming you have 32bit ints.

This is a really huge amount of memory and your best bet with standard C function is to request them via malloc() -- if your address space is large enough (on i386, it would be too small, but on amd64 it should be fine) and if the system can provide that much memory, the following should work:

int main(){

    unsigned long num_tests;
    scanf("%lu",&num_tests);

    int *array_n = malloc((size_t)num_tests * sizeof(*array));
    if (!array_n)
    {
        fputs("couldn't allocate array_n\n", stderr);
        return 1;
    }
    int *array_b = malloc((size_t)num_tests * sizeof(*array));
    if (!array_b)
    {
        fputs("couldn't allocate array_b\n", stderr);
        free(array_n);
        return 1;
    }

    size_t i,j;
    for (i=0;i<num_tests;i++){
        scanf("%d %d",&array_n[i],&array_b[i]);
    }

    // rest of code

    free(array_b);
    free(array_n);
}

Note I changed the scanf() to read an unsigned long, just to be sure. It's still not bullet-proof, though.

Answer 3

You don't need to store this data at all. Just process it on the fly.

As far as I can tell, the following code produces the same results as the code you posted, but uses no arrays whatsoever.

#include <stdio.h>

int main() {
    int k, t, N, B, max, num_tests;
    scanf("%d", &num_tests);
    while (num_tests--) {
        scanf("%d %d", &N, &B);
        for (k=N/B,max=0; k>0; k--) {
            t = (N-k*B) * k;
            if (t > max) max = t;
        }
        printf("%d\n", max);
    }
    return 0;
}

Answer 4

First of all, when you initialize an array the size must be constant. So use #define NUM_TESTS 1000000000 instead. Second, since an integers size is 4 bytes 10^9 integers would need 4 000 000 000 B which equals 4 GB. And its pretty 'hard' to 4 GB on the stack. You should use files or, if all your values are smaller than, lets say 256, you can use chars instead. Its still 1 GB, but thats way 'easier' to get.