CODEWITHSUNDEEP
javascriptarraysloops
Jonathan Joseph
Jonathan Joseph

Reputation: 57

Finding the highest divisible sum of elements in an array Javascript

I need to find the highest possible sum of numbers in an array passed to a function that can be divided with no remainder.

I am struggling to think of a way of iterating through an array of elements adding up all the possibilities and dividing by the parameter k which is the number for the division.

I thought of using a for loop and then passing the result to a variable on each iteration.

The part I can't get my head around is how to add all the possible combinations of the numbers in the array. As I can add them sequentially from the start of the array to the last element but not in all combinations such as element at index 0, element at index 3 etc.

I am fairly new to coding, explanations of how you could tackle the iteration challenge I have would be much appreciated.

function luckyCandies(prizes, k) {
  let sum = 0;
  let remainder = 0;
  let maxCandies = 0;
  let highestNumber = 0;

  prizes.sort(function(a, b) {
    return b - a;
  });

  for (let i = 0; i < prizes.length; i++) {
    sum = sum + prizes[i];
  }

  for (let i = 0; i < prizes.length; i++) {
    if (sum % k == 0) {
      sum = sum - prizes[i];
    }
  }

  console.log(sum);

  return sum;
}

Upvotes: 0

Views: 145

Answers (1)

Rukshan Jayasekara
Rukshan Jayasekara

Reputation: 1985

Implemented this solution for your use case based on the answers in this.

In the given link the solutions are for the highest possible sum of numbers given the divisible 3 but it won't be a problem since there is a proper in detailed explanation.

const maxSumDivByNo = (A, no) => {
    const K = Array(no).fill().map((v,i) => 0);
    for (let x of A) {
        let pre = [...K]; // create current from previous 🤔
        for (let y of pre)
            K[(x + y) % no] = Math.max(K[(x + y) % no], x + y); // add A[i] (ie. x) onto each previous bucket and update each current bucket to max of itself and the current sum (x + y)
    }
    return K[0]; // max sum of all N items of A which is evenly divisible by no 🎯
};

const A = [1, 2, 3, 4, 5];
const no = 5;
console.log(maxSumDivByNo(A, no)); // --> 15

const A1 = [1, 6, 2, 9, 5];
const no1 = 8
console.log(maxSumDivByNo(A1, no1)); // --> 16

Upvotes: 1

Related Questions