Search algorithm if the numbers in the list when adding or subtracting are equal to the modulus b

Question

I had problems with the interview when I came across an interesting one that I could not think of a solution to. The tasks indicated:

Create a function that takes an array of integers. The last two numbers in this array are "a" and "b". The function should find if all numbers in the array, when they are added / subtracted in any way, are equal to mod b, except for the last two numbers a and b.

So, let's say we have an array:

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

I need to find out if there is a possible “placement” in this array +/-so that the numbers can equal 3 mod 5. The function must print True for this array, because 5+4-3+3-1 = 8 = 3 mod 5.

An “obvious” and simple solution would be to try to add / subtract everything in all possible ways, but this is a complex integrated solution, possibly O (2 ⁿ ).

Is there any way to make this better?

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

Answer 1

O(b * n). Take your example [5, 4, 3, 3, 1]. Let it m[i][j]represent if a solution exists for jmod 5 before the index i:

i = 0:
5 = 0 mod 5
m[0][0] = True

i = 1: 
0 + 4 = 4 mod 5
m[1][4] = True

but we could also subtract

0 - 4 = 1 mod 5
m[1][1] = True

i = 2:

Explore previous opportunities:

m[1][4] and m[1][1]

4 + 3 = 7 = 2 mod 5
4 - 3 = 1 = 1 mod 5
1 + 3 = 4 = 4 mod 5
1 - 3 = -2 = 3 mod 5

m[2][1] = True
m[2][2] = True
m[2][3] = True
m[2][4] = True

i = 3:

1 + 3 = 4 mod 5
1 - 3 = 3 mod 5
2 + 3 = 0 mod 5
2 - 3 = 4 mod 5
3 + 3 = 1 mod 5
3 - 3 = 0 mod 5
4 + 3 = 2 mod 5
4 - 3 = 1 mod 5

m[3][0] = True
m[3][1] = True
m[3][2] = True
m[3][3] = True
m[3][4] = True

Actually, we could stop there, but let you choose a different solution than in your example back:

i = 4:

m[3][2] True means we had a solution for 2 at i=3
=> 2 + 1 means m[4][3] = True

+ 1
+ 3
+ 3
- 4

(0 - 4 + 3 + 3 + 1) = 3 mod 5

Answer 2

n , , O (b * n): k = 2 - n x , k x b.

k = 2 (a_0 + a_1) b (a_0 - a_1) b. k = 3, 4,..., n , . , , , .