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

Answer 2

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.

Answer 3

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.

Answer 4

import java.util.*;

public class MaxSumDivisible 
{

    static int max,divisor;

public static void main(String...okok)
{
    Scanner sc=new Scanner(System.in);
    String str=sc.nextLine();
    String ss[]=str.split(" ");
    LinkedList<Integer> list= new LinkedList<Integer>();
    for(int i=0;i<ss.length;i++)
    {
        list.add(Integer.parseInt(ss[i]));
    }
    divisor=sc.nextInt();
    FindMaxSum(list,0);
    System.out.println(max);
}
public static void FindMaxSum(LinkedList<Integer> list, int currentsum)
{
    if(currentsum%divisor==0 && currentsum>max)
    {
        max=currentsum;
    }

    for(int num:list)
    {
        LinkedList<Integer> li2= new LinkedList<Integer>(list);
        li2.remove(new Integer(num));
        FindMaxSum(li2,currentsum+num);

    }
}
}

It wil work for any numbers.(Only for int).

Answer 5

The following code is specifically for given number 3. ie. The sum of elements of array divisible by 3. You can generalize this further. The main idea is to track for each mod 3, the maximum sum that could be reached. Time Complexity: O(N). Space Complexity: O(K) where K is the int by which the sum should be divisible. Here K = 3.

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        dp[1] = dp[2] = Integer.MIN_VALUE;
        for(int x : nums) {
            int[] dpNext = new int[3];
            dpNext[0] = Math.max(dp[x%3] + x, dp[0]);
            dpNext[1] = Math.max(dp[(x+1)%3] + x,dp[1]);
            dpNext[2] = Math.max(dp[(x+2)%3] + x,dp[2]);
            dp = dpNext;
        }
        return dp[0];
    }
}

LeetCode Weekly Contest 163 Link to the problem.