#1300 - Sum of Mutated Array Closest to Target

Medium • View on LeetCode • View on GitHub

Problem Description

Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.

In case of a tie, return the minimum such integer.

Notice that the answer is not neccesarilly a number from arr.

Solution

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var findBestValue = function(arr, target) {
  arr.sort((a, b) => a - b);
  let prefixSum = 0;
  const length = arr.length;

  for (let i = 0; i < length; i++) {
    const remaining = length - i;
    const avg = (target - prefixSum) / remaining;

    if (avg <= arr[i]) {
      const floorVal = Math.floor(avg);
      const ceilVal = Math.ceil(avg);
      const floorSum = prefixSum + floorVal * remaining;
      const ceilSum = prefixSum + ceilVal * remaining;

      return Math.abs(floorSum - target) <= Math.abs(ceilSum - target) ? floorVal : ceilVal;
    }

    prefixSum += arr[i];
  }

  return arr[length - 1];
};