CODEWITHSUNDEEP
pythonalgorithmrecursiondynamic-programming
Surfero
Surfero

Reputation: 197

number of subsequences whose sum is divisible by k

I just did a coding challenge for a company and was unable to solve this problem. Problem statement goes like:

Given an array of integers, find the number of subsequences in the array whose sum is divisible by k, where k is some positive integer.

For example, for [4, 1, 3, 2] and k = 3, the solution is 5. [[3], [1, 2], [4,3,2], [4,2], [1,3,2]] are the subsequences whose sum is divisible by k, i.e. current_sum + nums[i] % k == 0, where nums[i] is the current element in the array.

I tried to solve this recursively, however, I was unable to pass any test cases. My recursive code followed something like this:

def kSum(nums, k):
    def kSum(cur_sum, i):
        if i == len(nums): return 0
        sol = 1 if (cur_sum + nums[i]) % k == 0 else 0
        return sol + kSum(cur_sum, i+1) + kSum(cur_sum + nums[i], i+1)
    return kSum(0, 0)

What is wrong with this recursive approach, and how can I correct it? I'm not interested in an iterative solution, I just want to know why this recursive solution is wrong and how I can correct it.

Upvotes: 1

Views: 2218

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

It seems to me that your solution is correct. It reaches the answer by trying all subsequences, which has 2^n complexity. We could formulate it recursively in an O(n*k) search space, although it could be more efficient to table. Let f(A, k, i, r) represent how many subsequences leave remainder r when their sum is divided by k, using elements up to A[i]. Then:

function f(A, k, i=A.length-1, r=0){
  // A[i] leaves remainder r
  // when divided by k
  const c = A[i] % k == r ? 1 : 0;

  if (i == 0)
    return c;
  
  return c +  
    // All previous subsequences 
    // who's sum leaves remainder r
    // when divided by k
    f(A, k, i - 1, r) +

    // All previous subsequences who's
    // sum when combined with A[i]
    // leaves remainder r when
    // divided by k
    f(A, k, i - 1, (k + r - A[i]%k) % k);
}

console.log(f([1,2,1], 3));
console.log(f([2,3,5,8], 5));
console.log(f([4,1,3,2], 3));
console.log(f([3,3,3], 3));

Upvotes: 0

Omega 16
Omega 16

Reputation: 21

Are you sure that is not the case test? For example: 

[4, 1, 3, 2], k = 3

has 

4+2 = 6, 1+2=3, 3, 1+2+3=6, 4+2+3 = 9

So, your function is right (it gives me 5) and I don't see a major problem with your function.

Upvotes: 1

vicatcu
vicatcu

Reputation: 5837

Here is a javascript reproduction of what you wrote with some console logs to help explain its behavior.

function kSum(nums, k) {
  let recursive_depth = 1;
  function _kSum(cur_sum, i) {
    recursive_depth++;
    
    if (i == nums.length) {
      recursive_depth--;
      return 0;
    }
    let sol = 0;
    if (((cur_sum + nums[i]) % k) === 0) {
      sol = 1;
      console.log(`Found valid sequence ending with ${nums[i]} with sum = ${cur_sum + nums[i]} with partial sum ${cur_sum} at depth ${recursive_depth}`);
    }
    const _kSum1 = _kSum(cur_sum, i+1);
    const _kSum2 = _kSum(cur_sum + nums[i], i+1);
    const res = sol + _kSum1 + _kSum2;
    
    recursive_depth--;
    return res; 
  }
  return _kSum(0, 0);
}

let arr = [4, 1, 3, 2], k = 3;
console.log(kSum(arr, k));

I think this code actually gets the right answer. I'm not fluent in Python, but I might have inadvertently fixed a bug in your code though by adding parenthesis around (cur_sum + nums[i]) % k

Upvotes: 0

Related Questions