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

Question

It is from a programming question.

The question is as follows:

An array of numbers will be given along with the number k we have to divide with. And we have to choose elements from that array such that the sum of those element is divisible by k. The sum of those elements should be as large as possible.

Input:

On the first line n, denoting the number of elements.

On the next line n numbers are given.

On the next line k is given by which we have to divide.

Output:

Largest sum as possible by choosing elements from that array s.t. sum is divisible by k.

Sample Input:

5 
1 6 2 9 5
8

Sample Output:

16

Note that 16 is obtainable by more than one combinations of numbers, but we're here concerned only about maximum sum.

My Proposed Solution:

I traverse over array and maintain cumulative sum in an array b for the given input array like:

b=[1 7 9 18 23]

and taking mod of numbers in array b by k and store it to

c=[1 7 1 2 7]

Now the numbers having the same value in c i.e. index 0 and index 2; index 1 and index 4. Now i have got all solutions, and the answer would be

max(b[2]-b[0],b[4]-b[1])

And is in a case three indexes have same value in c i.e. in case where

c=[1 2 3 1 1 2]

The answer would be

max(b[4]-b[0],b[5]-b[1])

Basically subtracting the leftmost occurrence of that number with the rightmost occurrence.

My solution only works if there are contiguos elements s.t. sum of elements is divisible by k. Expecting a description of the correct solution

Answer 1

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