CODEWITHSUNDEEP
javascriptarraysalgorithmnumbers
Snip3r
Snip3r

Reputation: 161

Find largest sum of 3 numbers which is also divisable by 3

How to find largest sum of 3 numbers which is also divisable by 3?
Examples:
Input: [1, 15, 4, 7, 2]
Output: [15, 7, 2] (In that order)

Input: [1, 2, 4, 7]
Output: [1, 4, 7] (In that order)

I came up only with this:

function largestSum(arr) {
    let max = -1;
    let nums;

    for (let i = 0; i < arr.length; i++)
        for (let j = i + 1; j < arr.length; j++)
            for (let k = j + 1; k < arr.length; k++)
                if ((arr[i] + arr[j] + arr[k]) % 3 === 0 && arr[i] + arr[j] + arr[k] > max)
                    nums = [arr[i], arr[j], arr[k]], max = arr[i] + arr[j] + arr[k];

    return nums;
}

But, isn't it better option here (with better efficiency)?

Upvotes: 1

Views: 391

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23955

This can be solved in linear time and constant space using modular arithmetic, no need to sort the input or enumerate its combinations.

Save:
  the largest three elements congruent to 0 mod 3
  the largest three elements congruent to 1 mod 3
  the largest three elements congruent to 2 mod 3

Choose the largest of:
  1. the sum of the largest three elements congruent to 0 mod 3
  2. the sum of the largest three elements congruent to 1 mod 3
  3. the sum of the largest three elements congruent to 2 mod 3
  4. the sum of the largest element congruent to 0 mod 3
                and the largest element congruent to 1 mod 3
                and the largest element congruent to 2 mod 3

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386560

Another simple solution with a simple combination algorithm and check for the wanted parameters.

function getCombinations(array) {
    function add(a, b) { return a + b; }

    function fork(i, t) {
        var sum = t.reduce(add, 0);
        if (i === array.length) {                
            if (t.length === 3 && sum % 3 === 0 && sum > result.reduce(add, 0)) {
                result = t;
            }
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

console.log(getCombinations([1, 15, 4, 7, 2]));
console.log(getCombinations([1, 2, 4, 7]));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 0

Rob Anthony
Rob Anthony

Reputation: 1813

If you sort the numbers first in descending order, then find the first solution which is divisible by three, this will be the largest value.

At it's worst, it's worse than your solution as it does everything yours does as well as sorting BUT at it's best it could be one sort and one test.

It's using the greedy algorithm.

Upvotes: 0

Amor
Amor

Reputation: 75

can't believe there is a way to do it without trying all the combinations of the array [what you've already done]

Upvotes: 0

Related Questions