1300. Sum of Mutated Array Closest to Target.md

1300. Sum of Mutated Array Closest to Target

---

leetcode-cn Daily Challenge on June 14, 2020.

---

Difficulty : Medium

---

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.

Example 1:

Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Example 2:

Input: arr = [2,3,5], target = 10
Output: 5

Example 3:

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

Constraints:

• 1 <= arr.length <= 10^4
• 1 <= arr[i], target <= 10^5

---

Solution

• mine
  • Java
    • Runtime: 6 ms, faster than 21.73%, Memory Usage: 44.9 MB, less than 5.17% of Java online submissions

      // O(N*logN)time 
      // O(N)space
      public int findBestValue(int[] arr, int target) {
          int len = arr.length;
          Arrays.sort(arr);
          int l = 0;
          while (l < len && arr[l] * (len - l) < target) {
              target -= arr[l];
              l++;
          }
          if (l == len) {
              return arr[len - 1];
          }
          int size = len - l;
          int avg = target / size;
          int t = avg * size;
          //t + size = (avg + 1) * size
          return t + size - target < target - t ? avg + 1 : avg;
      }
      

---

• the fastest solution in leetcode testcase
  • Runtime: 1 ms, faster than 99.60%, Memory Usage: 39.8 MB, less than 56.09% of Java online submissions

    //O(N^2)time O(1)space
    public int findBestValue(int[] arr, int target) {
        int big = 0;
        int sum = 0;
        for (int i : arr) {
            sum += i;
            big = big > i ? big : i;
        }
        if(sum <= target) return big;
        int ans = target / arr.length;
        sum = getSum(arr, ans);
        while(sum < target) {
            int sumn = getSum(arr, ans + 1);
            if(sumn >= target) return target - sum <= sumn - target ? ans : ans + 1;
            sum = sumn;
            ans++;
        }
        return 0;
    }
    
    public int getSum(int[] arr, int value) {
        int sum = 0;
        for (int i : arr) sum += i < value ? i : value;
        return sum;
    }