Finding greatest sum of elements of array which is divisible by a given number

Sounds like a variant of subset sum: you want the subset with the largest sum divisible by k.

Let dp[i] = largest sum obtainable that gives remainder i modulo k. However, in order to avoid using the same element twice, we must use two arrays because of the modulo: the array containing the current values of dp (dp1) and the array containing the previous values of dp (dp2). We have:

a = original array
dp1[*] = dp2[*] = 0 
for i = 1 to n do
  for j = k - 1 down to 0 do
    dp1[j] = max(dp1[j], dp2[(j - a[i]) mod k] + a[i])

  copy dp1 to dp2: on the next iteration, the current array will must become the
  previous one (*)

(*) Note that you do not necessarily have to do any copying if execution time is very important. You can use an array dp[2, k] and use its lines alternatively: computer from dp[0, _] to dp[1, _] in odd iterations, and the other way around in even iterations.

The answer will be in either of dp1[0, 0] or dp2[0, 0]. The memory used is O(n + k) and the time complexity O(n * k).

Note: when implementing this, you might need to do the modulo this way in order to avoid negative values: ((j - a[i]) mod k + k) mod k. Or you can use an if and only add k if the initial value is negative.


I believe your solution is not correct, since you're only considering consecutive numbers. For example, if the input is

4
1 6 2 9
8

The answer would still be 16 (=1+6+9). I'm not sure whether your solution can give this answer.

For an efficient solution for this problem, try dynamic programming. I would omit the details but point out the essentials.

Suppose the numbers are in an array a[i] where i is from 1 to n.

Let f(i,j) denote the largest sum you can get by choosing numbers from a[1] through a[i] (i.e. a[1], a[2], ..., a[i]) and also the sum modulo k is j.

Consider f(i,j), obviously we have two choices: (1) include a[i] in the sum; (2) do not include a[i]. Thus f(i,j) = max{ f(i-1,x) + a[i], f(i-1,j) } where x + a[i] == j (mod k). The boundary is f(0,j) = 0 for all j

To implement this algorithm, the basic skeleton is as follows.

for (j = 0; j < k; j++) f[0][j] = 0;
for (i = 1; i <= n; i++)
  for (j = 0; j < k; j++) {
    x = (j + k - a[i]%k) % k;
    f[i][j] = max(f[i-1][x], f[i-1][j]);
  }

In order to save memory, you can also use an array of size [2][k] instead of [n][k]:

for (j = 0; j < k; j++) f[0][j] = 0;
for (i = 1; i <= n; i++)
  for (j = 0; j < k; j++) {
    x = (j + k - a[i]%k) % k;
    f[i%2][j] = max(f[(i-1)%2][x], f[(i-1)%2][j]);
  }

You can also use i&1 (and (i-1)&1) to speed up modulo of 2.

Further references on dynamic programming:

  • A Tutorial on TopCoder: Dynamic Programming: From novice to advanced
  • Dynamic Programming - A Computational Tool by Prof. Art Lew and Dr. Holger Mauch
  • Dynamic Programming - Foundations and Principles by Moshe Sniedovich

Note: for the special case when the number is 3, the answer can easily be found in O(n log n) time.

Let S = sum(array).
Now, if S % 3 == 0, then S is the answer.
If S % 3 == 1, then to make the sum divisible by 3 you can either remove the smallest element i such that i % 3 == 1, or remove the smallest j, k such that j % 3 == k % 3 == 2.
If S % 3 == 2, then you can either remove the smallest i such that i % 3 == 2, or the smallest j, k such that j % 3 == k % 3 == 1.

Tags:

Algorithm

Dynamic Programming

Recent Posts