Sum of mutated array closest to target

Array Binary Search Sorting

46.2% acceptance

Feb 25, 2026

1204

155

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

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_best_value(mut arr: Vec<i32>, target: i32) -> i32 {
    arr.sort();
    let n = arr.len();
    // Build prefix sums
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + arr[i] as i64;
    }

    let sum_with_value = |v: i32| -> i64 {
      // Binary search for first index where arr[idx] > v
      let pos = arr.partition_point(|&x| x <= v);
      prefix[pos] + (n - pos) as i64 * v as i64
    };

    let mut lo = 0i32;
    let mut hi = *arr.last().unwrap();
    let mut ans = 0;
    let mut best_diff = i64::MAX;

    while lo <= hi {
      let mid = (lo + hi) / 2;
      let s = sum_with_value(mid);
      let diff = (s - target as i64).abs();
      if diff < best_diff || (diff == best_diff && mid < ans) {
        best_diff = diff;
        ans = mid;
      }
      if s < target as i64 {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    ans
  }
}