Largest sum divisible by n

I asked this question on StackOverflow, but I think here is a more appropriate place.

This is a problem from Introduction to algorithms course:

You have an array $a$ with $n$ positive integers (the array doesn't need to be sorted or the elements unique). Suggest an $O(n)$ algorithm to find the largest sum of elements that is divisible by $n$.

Example: $a = [6, 1, 13, 4, 9, 8, 25], n = 7$. The answer is $56$ (with elements $6, 13, 4, 8, 25$)

It's relatively easy to find it in $O(n^2)$ using dynamic programming and storing largest sum with remainder $0, 1, 2,..., n - 1$.

Also, if we restrict attention to a contiguous sequence of elements, it's easy to find the optimal such sequence in $O(n)$ time, by storing partial sums modulo $n$: let $S[i]=a[0]+a[1]+\dots + a[i]$, for each remainder $r$ remember the largest index $j$ such that $S[j] \equiv r \pmod{n}$, and then for each $i$ you consider $S[j]-S[i]$ where $j$ is the index corresponding to $r=S[i] \bmod n$.

But is there a $O(n)$-time solution for the general case? Any suggestions will be appreciated! I consider this has something to deal with linear algebra but I'm not sure what exactly.

Alternatively, can this be done in $O(n \log n)$ time?

• 1. You've posted the exact same question on Stack Overflow. Please do not post the same question on multiple sites. We don't want multiple copies floating around on multiple SE sites. If you didn't get an acceptable answer, it's OK to flag your question for migration to another site, but please don't just repost the same thing elsewhere. 2. Can you give a reference/citation/link to the textbook or course where this appeared? How sure are you that there does exist a $O(n)$-time solution? – D.W. Mar 7 '16 at 21:58
• Is the challenge on your university still open? It would be really helpful to see link to the course, exact question and if it is really $O(n)$ and people who prepared it will explain/publish their answer it would be awesome. – Evil Mar 9 '16 at 6:25
• It's relatively easy to find it in O(n2)O(n2) using dynamic programming and storing largest sum with remainder 0,1,2,...,n−10,1,2,...,n−1. Could you please elaborate this a bit? I can understand how this would be n-squared if we only consider contiguous elements, but with non-contiguous elements as well, wouldn't it be exponential in order? – Nithish Inpursuit Ofhappiness Jul 13 '17 at 21:35

Here are a few random ideas:

• The dynamic-programming algorithm can be flipped to look for a smallest sum instead of a largest sum. You just end up looking for a sum congruent to the remainder of the sum of the entire array, instead of one congruent to zero. If we process the elements in increasing order, this sometimes allows the dynamic algorithm to terminate before processing the entire array.

The cost would be $O(n k)$ if we processed $k$ elements. There's not a lower bound of $\Omega(n \log n)$ on this algorithm because we don't have to sort all the elements. It only takes $O(n \log k)$ time to get the $k$ smallest elements.

• If we cared about the set with the larget size, instead of the set with the largest sum, we might be able to use fast-fourier-transform-based polynomial multiplication to solve the problem in $O(n (\log n)^2 (\log \log n))$ time. Similar to what's done in 3SUM when the domain range is limited. (Note: use repeated squaring to do a binary search, else you'll get $O(n k (\log n) (\log \log n))$ where $k$ is the number of omitted elements.)

• When $n$ is composite, and almost all remainders are a multiple of one of $n$'s factors, significant time might be saved by focusing on the remainders that aren't a multiple of that factor.

• When a remainder r is very common, or there are only a few remainders present, keeping track of 'next open slot if you start from here and keep advancing by r' information can save a lot of scanning-for-jumps-into-open-spots time.

• You can shave a log factor by only tracking reachability and using bit masks (in the flipped dynamic algorithm), then backtracking once you reach the target remainder.

• The dynamic programming algorithm is very amenable to being run in parallel. With a processor for each buffer slot you can get down to $O(n)$. Alternatively, by using $O(n^2)$ breadth, and divide and conquer aggregation instead of iterative aggregation, the circuit depth cost can get all the way down to $O(\log^2 n)$.

• (Meta) I strongly suspect that the problem you were given is about contiguous sums. If you linked to the actual problem, it would be easy to verify that. Otherwise I'm very surprised by how difficult this problem is, given that it was assigned in a course called "Introduction to Algorithms". But maybe you covered a trick in class that makes it trivial.

• For point one. It's not written in the specifications of the problem, so you can't assume that. Also, the problem is not saying that you can't modify the array or create new ones, you can indeed. The only thing you need to do is find the numbers that summed together give you the largest sum that is divisible by $n$ in $O(n)$ time complexity (usually it's assumed just the time complexity). – nbro Mar 8 '16 at 9:36
• @EvilJS The subset with the largest sum with remainder 0 is equal to the full set after removing the subset with the smallest sum with remainder congruent to the full set's sum. Looking for a smallest sum congruent to $r_1$ is more convenient than looking for a largest sum congruent to $r_2$ because it allows you to terminate as soon as you find a solution (when processing elements in increasing order) instead of having to continue. – Craig Gidney Mar 8 '16 at 18:50

My proposed algorithm goes as follows:

A sum is divisible by n if you only add summands which are multiples of n.

Before you start you create a hashmap with an int as key and a list of indices as value. You also create a resultlist containing indices.

You then loop over the array and add every index which mod n is zero to your result list. For every other index you do the following:

You subtract the value mod n of this index from n. This result is the key for your hashmap which stores indices for elements with the required value. Now, you add this index to the list in the hashmap and move on.

After you finished looping over the array you compute the output. You do this by sorting each list in the hashmap according to the value the index points to. Now you consider every pair in the hashmap summing up to n. So if n = 7 you search the hashmap for 3 and 4. If you got an entry in both you take the two largest values remove them from their lists and add them to your resultlist.

Last recommendation: still didn't test the algorithm, write a testcase against it using a brute force algorithm.

• Greedy, linear, not working. You consider only elements that are divisible by n and pairs divisible by n, what about triples and more? It does not guarantee maximal subset sum on trivial case. [2, 1, 8] -> maximal sum is 9, but your algorithm returns 3. – Evil Mar 9 '16 at 0:24
• @EvilJS what happened with your sub-$n^2$ algorithm? – delta-terminator Mar 9 '16 at 0:38
• Thanks for pointing this mistake out to me. My idea on improvement would be to make a hashmap of stacks of lists which is ordered by increasing value and start accumulating only after completing a pass through the array. – Tobias Würfl Mar 9 '16 at 19:37
• You mean array of arrays, which will be sorted, and "hashmap" is % n? You still need to sort them, and if you have them sorted, taking minimal / maximal value is ok, but still there is inevitable part of actually choosing subset, which in the worst case does not benefit. Anyway if you have some improvements, maybe you could edit post? – Evil Mar 9 '16 at 22:14
• Yeah was quite a quick idea with the stacks. In fact you only need lists in the hashmap which you sort. I was not sure wether it is polite to edit my first answer. After all I made a mistake in my first attempt. – Tobias Würfl Mar 10 '16 at 21:36

use this DP method from (https://stackoverflow.com/questions/4487438/maximum-sum-of-non-consecutive-elements?rq=1):

Given an array A[0..n], let M(i) be the optimal solution using the elements with indices 0..i. Then M(-1) = 0 (used in the recurrence), M(0) = A[0], and M(i) = max(M(i - 1), M(i - 2) + A[i]) for i = 1, ..., n. M(n) is the solution we want. This is O(n). You can use another array to store which choice is made for each subproblem, and so recover the actual elements chosen.

Change recursion to M(i) = max(M(i - 1), M(i - 2) + A[i] ) such that is stored only if its divisible by N

• This doesn't work – I'll let you figure out why. (Hint: Try to run it on the constant 1 array.) Also, in this problem we do allow consecutive elements. – Yuval Filmus Mar 10 '16 at 22:42
• This is very good solution, just to totally different (and much easier) problem. – Evil Mar 10 '16 at 23:05