Sum divisible by n

Question

This is a problem from Introduction to algorithms course:

You have an array with n random 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.

It's relatively easy to find it in O(n²) using dynamic programming and storing largest sum with remainder 0, 1, 2,..., n - 1. This is a JavaScript code:

function sum_mod_n(a)
{
    var n = a.length;

    var b = new Array(n);
    b.fill(-1);

    for (var i = 0; i < n; i++)
    {
        var u = a[i] % n;
        var c = b.slice();

        for (var j = 0; j < n; j++) if (b[j] > -1)
        {
            var v = (u + j) % n;
            if (b[j] + a[i] > b[v]) c[v] = b[j] + a[i];
        }

        if (c[u] == -1) c[u] = a[i];
        b = c;
    }

    return b[0];
}

It's also easy to find it in O(n) for contiguous elements, storing partial sums MOD n. Another sample:

function cont_mod_n(a)
{
    var n = a.length;

    var b = new Array(n);
    b.fill(-1);

    b[0] = 0;

    var m = 0, s = 0;

    for (var i = 0; i < n; i++)
    {
        s += a[i];
        var u = s % n;
        if (b[u] == -1) b[u] = s;
        else if (s - b[u] > m) m = s - b[u];
    }

    return m;
}

But how about O(n) in 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.

EDIT: Can this actually be done in O(n log n)?

Answer 1

Since you don't specify what random means (uniform? if so in what interval?) the only general solution is the one for arbitrary arrays and I don't think you can get any better than O(n²). This is the dynamic programming algorithm in Python:

def sum_div(positive_integers):
    n = len(positive_integers)
    # initialise the dynamic programming state
    # the index runs on all possible reminders mod n
    # the DP values keep track of the maximum sum you can have for that reminder
    DP = [0] * n
    for positive_integer in positive_integers:
        for remainder, max_sum in list(enumerate(DP)):
            max_sum_next = max_sum + positive_integer
            remainder_next = max_sum_next % n
            if max_sum_next > DP[remainder_next]:
                DP[remainder_next] = max_sum_next
    return DP[0]

You can probably work out a faster solution if you have an upper limit for the values in the array, e.g. n.