Minimize sum of array by applying specific operation on x carefully chosen elements

Question

This code works, and solves the problem, but doesn't satisfy some time requirements, especially when the 'nums' array can have a length of over 1000. How can this be optimized?

Just reference: This function does x number of operations on any element in the nums array so that the sum of all elements in the final array is always as small as possible. As a result, you have to perform the operation on the elements with the highest values first.

function minSum(nums, x) {
    if (nums.length === 0) {
        return false;
    }
    function operation(max) { 
        let redcuedMax = Math.floor(max / 10);
        return redcuedMax
    }
    let ops = x;
    while (ops > 0) {
        let max = Math.max(...nums);
        const ofNumber = (element) => element >= max ;
        let maxIndex = nums.findIndex(ofNumber)
        let operated = operation(max);
        nums[maxIndex] = operated;
        ops--
    }
    return nums.reduce((prev,next) => prev + next, 0)
}

minSum([400,209,77], 4) //out: 31
minSum([5000,5000,5000,5000,5000,], 4) //out: 7000

Answer 1

First let me point out a few details.

Use const intead of let unless you are going to modify the value after initialization. You use it for the ofNumber variable, but there are more that deserve it.

But actually there's often no need to define a variable at all if it is used only once. Similarily, storing a return value to a variable and immediately returning that variable is redundant, just return the value returned by the function directly.

function operation(max) {
    return Math.floor(max / 10);
}

But you could also stay consistent with the ofNumber callback like this:

const operation = (max) => Math.floor(max / 10);

Another thing is that we usualy use for loop in theese cases.

for (let ops = x; ops > 0; --ops) {...}

Now, let's analyse the big-O time complexity of your algorithm. Adding a comment above each statement in your code. n=nums.length.

function minSum(nums, x) {
    // O(1)
    if (nums.length === 0) {
        return false;
    }
    function operation(max) {
        // O(1)
        let redcuedMax = Math.floor(max / 10);
        return redcuedMax
    }
    let ops = x;
    // O(x * inner)
    while (ops > 0) {
        // O(n)
        let max = Math.max(...nums);
        // O(1)
        const ofNumber = (element) => element >= max ;
        // O(n)
        let maxIndex = nums.findIndex(ofNumber)
        // O(1)
        let operated = operation(max);
        // O(1)
        nums[maxIndex] = operated;
        // O(1)
        ops--
    }
    // O(n)
    return nums.reduce((prev,next) => prev + next, 0)
}

That makes for O(x * n) in time. O(1) in space of course, because you are never making any copies of the array.

How can we optimize this?

Well first thing i see is that there are 2 O(n) operations in the loop body. Maybe we can find the maximum's element index in O(n).And if we do, we can access the maximum element in O(1). This optimization will be less efective if the input is sorted or almost sorted in descendant order, because the second O(n) operation is basically O(1) for such sorted input.

Another thing is that after the loop, there is another O(n) operation. Maybe we can keep track of the sum (updating it in O(1) time) ever since the first time we needed to scan the entire array. Although, this optimization is x times less significant, for small x it may help.

Of course, the most significant improvement can only arise from changing the entire algorithm's big-O complexity from O(x * n) to something with slower rate of change. Even if it costs us increased memory complexity to say O(n).

To do that we have to leave the code for now and let's think about the problem itself.

You wrote:

As a result, you have to perform the operation on the elements with the highest values first.

Good. But is there more? How many of the highest elements will you actually need?

At most x, right? Either the highest element divided by 10 remains the highest element, in which case you continue with that one, or the next highest element will become the current highest. So maybe we dont want to track just 1 highest element, but x of them. This may raise our memory complexity to O(min(x,n)), but that would be still a good tradeoff.

Well, and I think I will break off at this point. I don't wanna write it for you. I hope I gave you enough hints to come up with a faster solution on your own. Just one more thing to say, don't be afraid to use your own specialized loops in such optimizations even if it means your code will grow. It's always trade-offs. Time, space, readability/code size, ... you improve one, you loose on the other... well sometimes not if you got it very wrong on the first shot :D (not saying this is the case:)).

EDIT: I found this article (https://www.google.com/amp/s/www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/amp/) which shows several ways to find the x largest elements of an array, some of them seem to be faster then actually sorting the entire array in O(n * log(n)).

Answer 2

• You can simplify the code (and maybe accelarate it) by not assigning variables for values that are used once.
• spreading the nums array is slow (Math.max), see also. Math.max with spreading or the faster alternative (Math.max.apply) for a larger array (somewhere between 120.000 - 130.000 elements) will throw a Range Error, so use a loop for it.
• reduce is (a lot) slower than a regular loop, so use a loop to determine the sum
• Math.floor can be replaced by a bitwise operator (it's slightly faster)
• Side note: alway use semicolons

The first snippet shows the aforementioned optimizations

const testLongerArray = [...Array(2000)].map((v, i) => i && i*10 || 1);
const testVeryLongArray = [...Array(200000)].map((v, i) => i && i*10 || 1);
console.log(minSum(testLongerArray, 600)); // out 10812701
console.log(minSum(testVeryLongArray, 1600)); // out 197130527201
console.log(minSum([209,400,77], 4)); //out: 31
console.log(minSum([5000,5000,5000,5000,5000,], 4)); //out: 7000

function maxValue(arr) {
  let max = 0;
  let i = arr.length;
  while (i--) {
    max = arr[i] > max && arr[i] || max;
  }
  return max;
};

function minSum(nums, x) {
    if (nums.length === 0) {
        return false;
    }
    const start = performance.now();
    
    while (x--) {
        // Note: a loop for max is the fastest
        // and for very large arrays spreading and Math.max.apply
        // will throw, so using the loop here
        const max = maxValue(nums);
        const maxIndex = nums.indexOf(max);
        //               ^ use indexOf
        nums[maxIndex] = (max / 10) | 0;
        //               ^ Math.floor replacement
    }
    
    // replace reduce with a loop
    let len = nums.length;
    let sum = 0;
    
    while (len--) {
      sum += nums[len];
    }

    return `sum: ${sum}, time: ${(performance.now() - start).toFixed(2)} ms`;
}

Now you don't have to iterate through the whole array. If you sort the input array descending, you can take a subset of the first [x length] elements of the sorted input array and perform the operation on the elements of that subset. Adding up the subset elements and the elements of the original sorted array minus its first x elements should give the desired result.

That's worked out in the second snippet. In both snippets the performance is timed, so you can compare both snippets (especially for the longer arrays).

const testLongerArray = [...Array(2000)].map((v, i) => i && i * 10 || 1);
const testVeryLongArray = [...Array(200000)].map((v, i) => i && i * 10 || 1);
console.log(minSum(testLongerArray, 600)); // out 10812701
console.log(minSum(testVeryLongArray, 1600)); // out 197130527201
console.log(minSum([209, 400, 77], 4)); //out: 31
console.log(minSum([5000, 5000, 5000, 5000, 5000, ], 4)); //out: 7000

function minSum(nums, x) {
  if (nums.length === 0) {
    return false;
  }
  const start = performance.now();
  const operation = v => (v / 10) | 0;
  nums.sort((a, b) => b - a);
  let subset = nums.slice(0, x);
  let sum = 0;
  nums = nums.slice(x);

  while (x--) {
    const maxVal = maxValue(subset);
    subset[subset.indexOf(maxVal)] = operation(maxVal);
  }
  nums = nums.concat(subset);
  x = nums.length;
  
  while (x--) {
    sum += nums[x];
  }

  return `sum: ${sum}, time: ${(performance.now() - start).toFixed(2)} ms`;
}

function maxValue(arr) {
  let max = 0;
  let i = arr.length;
  while (i--) {
    max = arr[i] > max && arr[i] || max;
  }
  return max;
}