How to check if an integer is linear combination o

Question

How to check if an integer can be expressed as linear combination of elements in a given array of length n? Currently I can code for the specific case when n=2, but I don't know how to code when n is unknown.

This is the function when n=2 (when there are only two elements in the array):

bool check(int array[], int n, int value){//n values in the array //    

  for (int i=1; i<array[0]; i++){
     for (int j=1; j<array[1]; j++){
        if ((i*array[0]+j*array[1])%value==0){
            printf("x=%d, y=%d, i=%d, j=%d\n", array[0], array[1], i, j);
            return 1;
        }
    }
    }
return 0;
}

Answer 1

I remember from my first-year discrete math courses that n is a linear combination of x and y if and only if n is a multiple of the gcd(x,y) (i.e. if value % gcd(x,y) == 0)

you can use this notion as a powerful asset in your code.

The moral here is to calculate the gcd between all the elements in your set and keep checking if value is divisible by the gcd(x,y). If it is, then return 1, else 0.

I'll leave the implementation of the gcd() function to you (there are many examples of it online), but here is how you can incorporate it in your existing code:

bool check(int array[], int n, int value){
    for (int i = 0; i < n - 1; i++) {            // notice we only iterate up to n - 1
        for (int j = i + 1; j < n; j++) {
            if (value % gcd(array[i], array[j]) == 0) {
               printf("x=%d, y=%d, i=%d, j=%d\n", array[0], array[1], i, j);
               return 1;
            }
        }  
    }
    return 0;
}