CODEWITHSUNDEEP
algorithmdynamic-programmingmodulo
delta-terminator
delta-terminator

Reputation: 193

Sum divisible by n

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(n2) 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)?

Upvotes: 15

Views: 2056

Answers (2)

Sandro Rosa
Sandro Rosa

Reputation: 517

Very interesting question ! This is my JS code. I don't think that O(n^2) can be lowered, hence I suppose that the way is to find an algorithm being more efficient in terms of benchmarking.

My (corrected) approach boils down to explore paths of sums until the next matching one (i.e. divisible by _n) is computed. The source array progressively shrinks as next sums are found.

(I provided different examples at the top)

var _a = [1000, 1000, 1000, 1000, 1000, 1000, 99, 10, 9] ;
//var _a = [1000, 1000, 1000, 1000, 1000, 1000, 99, 10, 9, 11] ;
//var _a = [1, 6, 6, 6, 6, 6, 49] ;
//var _a = [ -1, 1, 2, 4 ] ;
//var _a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] ;
//var _a = [1,1,1,1,1,1] ;
var _n = _a.length, _del_indexes = [] ;
var _rec = 0, _sum = 0, _start = 0, _test = 0 ;

console.log( "input array : ", _a );
console.log( "cardinality : ", _a.length );

while( _start < _a.length )
{
    _test = 0 ;
    for( var _i = _start ; _i < _a.length ; _i++ )
    {
             _sum += _a[_i%_n] ;
             _del_indexes.push( _a[_i%_n] );
             if ( ( _sum % _n ) == 0 )
             {
                 _rec = _sum ;
                 _test = 1 ;
                 break ;
             }
    }

    if ( _test )
    {
        for( var _d = 0 ; _d < _del_indexes.length ; _d++ ) _a.splice( _a.indexOf( _del_indexes[_d] ), 1 ) ;
        _start = 0 ;
    }
    else _start++ ;

    _del_indexes = [] ;
    _sum = _rec ;
}

console.log( "Largest sum % " + _n + " is : ", _rec == 0 ? "none" : _rec );

Upvotes: 0

alexamici
alexamici

Reputation: 784

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(n2). 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.

Upvotes: 1

Related Questions