Designing an algorithm that determines if the numbers in the list are equal to a mod b

Question

I was doing some interview problems when I ran into an interesting one that I could not think of a solution for. The problems states:

Design a function that takes in an array of integers. The last two numbers in this array are 'a' and 'b'. The function should find if all of the numbers in the array, when summed/subtracted in some fashion, are equal to a mod b, except the last two numbers a and b.

So, for example, let us say we have an array:

array = [5, 4, 3, 3, 1, 3, 5].

I need to find out if there exists any possible "placement" of +/- in this array so that the numbers can equal 3 mod 5. The function should print True for this array because 5+4-3+3-1 = 8 = 3 mod 5.

The "obvious" and easy solution would be to try and add/subtract everything in all possible ways, but that is an egregiously time complex solution, maybe O(2ⁿ).

Is there any way better to do this?

Edit: The question requires the function to use all numbers in the array, not any. Except, of course, the last two.

Answer 1

Sketch:

If you're doing this modulo $n=5$ (or another small number), create a series of arrays $A_{k}$ of length $n$ with the following property:

$A_k[i]=0$ if $i$ cannot be written as a sum/difference of the first $k$ integers and $A_k[i]=1$ if $i$ can be written as a sum/difference of the first $k$ integers.

It is fairly easy to update from $A_{k-1}$ to $A_k$ because if $j$ is the $k$th integer, then all you need to do is put $1$'s at $i+j$ and $i-j$ (modulo $n$) whenever $A_{k-1}[i]=1$.

You can really do this with two arrays by switching back and forth.

The trick is that you need to know if a sum is possible, not how to actually sum it. So you don't need to know what the $+/-$'s are, only that it's possible.

In your example:

\begin{align} A_0&=[1,0,0,0,0]\\ A_1&=[1,0,0,0,0]\\ A_2&=[0,1,0,0,1]\\ A_3&=[0,1,1,1,1]\\ A_4&=[1,1,1,1,1]\\ A_5&=[1,1,1,1,1] \end{align} Therefore, anything is possible modulo $5$ with the given sequence.

$A_0$ is $1$ in the $0$ spot and $0$'s elsewhere since the empty sum is possible, but nothing else. $A_1$ has positions $0+5$ and $0-5$ turned on, but they're both $0$. $A_2$ has positions $0+4$ and $0-4$ turned on. $A_3$ has positions $1+3$, $1-3$, $4-3$, and $4+3$ turned on, and so on.