# Divisibility and recurrence

the brute force will give 2^n solution n=10^4 so there should have to be a dynamic programming solution

can anyone help me to make the dynamic equation of this problem

a) For each number, we add add it or subtract it to the current result.
b) We’re interested in divisibility by K. In other words, we want to know if the remainder is zero.

So, the search state is the current number and the remainder of our expression divided by K. N <= 10^4 and K <= 10^2 yields 10^6 states which is fine as we only need O(1) per state (add and subtract the number to current remainder).

A simple pseudo-c++ would be

``````bool seen[N][K];  // init to false
bool IsDivisible(pos, remainder) {
if seen[pos][remainder]
return false  // we've seen before this state leads nowhere
if pos == N
return remainder == 0
seen[pos][remainder] = true
if IsDivisible(pos+1, (remainder + number[pos]) % K)
return true
if IsDivisible(pos+1, (remainder - number[pos] + K) % K)
return true
return false
}
// call it with IsDivisible(0, 0)``````
1 Like