Find the Sum of Mutated Array Closest to Target
Given an integer array arr[] and a target value target. The task is to return an integer value such that when you change all the integers in the array that are larger than this value to be equal to the value, the sum of the modified array gets as close as possible (in absolute difference) to the target value. In the case of a tie, where multiple values result in the same minimum absolute difference from the target, you should return the minimum of those values.
Note: It’s important to note that the answer you return is not necessarily a number that is already present in the given arr array.
Example:
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.Input: arr = [2,3,5], target = 10
Output: 5Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361
Approach:
The idea is to perform a binary search on the possible values of the answer. Let the answer be x, then we need to find the minimum value of x such that the sum of the modified array is greater than or equal to the target value.
Steps-by-step approach:
- Initialize the range of possible values of x as [0, max(arr)] where max(arr) is the maximum value in the input array arr.
- Perform binary search on the range [lo, hi], where lo and hi are the lower and upper bounds of the range.
- In each iteration of the binary search, calculate the sum of the modified array for the current value of x.
- If the sum is greater than or equal to the target, set the upper bound of the range as the current value of x. Otherwise, set the lower bound of the range as the current value of x + 1.
- After the binary search, calculate the sum of the modified array for the two possible values of x (lo and lo – 1) and return the value of x that minimizes the absolute difference between the sum and the target.
Below is the implementation of the above approach:
#include <algorithm> // for std::abs
#include <iostream>
#include <vector>
using namespace std;
// Function to find the best value (closest to the target)
// from the array
int findBestValue(vector<int>& arr, int target)
{
int n = arr.size();
// Find the highest value in the array
int hi = *max_element(
arr.begin(), arr.end()); // using std::max_element
// Binary search to find the closest value
int lo = 0, mid;
while (lo < hi) {
mid = lo + (hi - lo) / 2;
int sum = 0;
// Calculate the sum considering the minimum between
// element and mid
for (int i = 0; i < n; i++) {
sum += min(arr[i], mid);
}
if (sum >= target) {
hi = mid; // If sum is enough or more, target
// might be closer to lower values
}
else {
lo = mid + 1; // If sum is less, target might be
// closer to higher values
}
}
// Calculate sum considering minimum between element and
// lo (potential best value) and minimum between element
// and lo-1 (alternative candidate)
int sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i++) {
sum1 += min(arr[i], lo);
sum2 += min(arr[i], lo - 1);
}
// Return the value (lo or lo-1) that gives a sum closer
// to the target
return abs(sum2 - target) <= abs(sum1 - target) ? lo - 1
: lo;
}
int main()
{
vector<int> arr = { 4, 9, 3 };
int target = 10;
int best_value = findBestValue(arr, target);
cout << "The best value (closest to target " << target
<< ") is: " << best_value << endl;
return 0;
}
import java.util.Arrays;
public class Main {
// Function to find the best value (closest to the
// target) from the array
static int findBestValue(int[] arr, int target)
{
int n = arr.length;
// Find the highest value in the array
int hi = Arrays.stream(arr).max().getAsInt();
// Binary search to find the closest value
int lo = 0, mid;
while (lo < hi) {
mid = lo + (hi - lo) / 2;
int sum = 0;
// Calculate the sum considering the minimum
// between element and mid
for (int i = 0; i < n; i++) {
sum += Math.min(arr[i], mid);
}
if (sum >= target) {
hi = mid; // If sum is enough or more,
// target might be closer to lower
// values
}
else {
lo = mid
+ 1; // If sum is less, target might be
// closer to higher values
}
}
// Calculate sum considering minimum between element
// and lo (potential best value) and minimum between
// element and lo-1 (alternative candidate)
int sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i++) {
sum1 += Math.min(arr[i], lo);
sum2 += Math.min(arr[i], lo - 1);
}
// Return the value (lo or lo-1) that gives a sum
// closer to the target
return Math.abs(sum2 - target)
<= Math.abs(sum1 - target)
? lo - 1
: lo;
}
public static void main(String[] args)
{
int[] arr = { 4, 9, 3 };
int target = 10;
int bestValue = findBestValue(arr, target);
System.out.println(
"The best value (closest to target " + target
+ ") is: " + bestValue);
}
}
import bisect
from typing import List
def findBestValue(arr: List[int], target: int) -> int:
n = len(arr)
# Find the highest value in the array
hi = max(arr)
# Binary search to find the closest value
lo = 0
while lo < hi:
mid = lo + (hi - lo) // 2
sum = 0
# Calculate the sum considering the minimum between
# element and mid
for i in range(n):
sum += min(arr[i], mid)
if sum >= target:
hi = mid # If sum is enough or more, target
# might be closer to lower values
else:
lo = mid + 1 # If sum is less, target might be
# closer to higher values
# Calculate sum considering minimum between element and
# lo (potential best value) and minimum between element
# and lo-1 (alternative candidate)
sum1 = 0
sum2 = 0
for i in range(n):
sum1 += min(arr[i], lo)
sum2 += min(arr[i], lo - 1)
# Return the value (lo or lo-1) that gives a sum closer
# to the target
return lo - 1 if abs(sum2 - target) <= abs(sum1 - target) else lo
if __name__ == "__main__":
arr = [4, 9, 3]
target = 10
best_value = findBestValue(arr, target)
print(f"The best value (closest to target {target}) is: {best_value}")
# This code is contributed by Ayush Mishra
function findBestValue(arr, target) {
const n = arr.length;
// Find the highest value in the array
let hi = Math.max(...arr);
// Binary search to find the closest value
let lo = 0;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
let sum = 0;
// Calculate the sum considering the minimum
// between element and mid
for (let i = 0; i < n; i++) {
sum += Math.min(arr[i], mid);
}
if (sum >= target) {
hi = mid; // If sum is enough or more,
// target might be closer to lower
// values
} else {
lo = mid + 1; // If sum is less, target might be
// closer to higher values
}
}
// Calculate sum considering minimum between element
// and lo (potential best value) and minimum between
// element and lo-1 (alternative candidate)
let sum1 = 0, sum2 = 0;
for (let i = 0; i < n; i++) {
sum1 += Math.min(arr[i], lo);
sum2 += Math.min(arr[i], lo - 1);
}
// Return the value (lo or lo-1) that gives a sum
// closer to the target
return Math.abs(sum2 - target) <= Math.abs(sum1 - target)
? lo - 1
: lo;
}
const arr = [4, 9, 3];
const target = 10;
const bestValue = findBestValue(arr, target);
console.log(`The best value (closest to target ${target}) is: ${bestValue}`);
Output
The best value (closest to target 10) is: 3
Time complexity: O(n log(max(arr))), where n is the length of the input array and max(arr) is the maximum value in the input array.
Auxiliary Space : O(1) since we are only using constant extra space.
Contact Us