Find the maximum possible value of the minimum value of a modified array in C++

In this problem, we are given an array arr[] of size n and a number S. Our task is to find the maximum possible value of the minimum value of the modified array. p>

Here are the rules for modifying the array.

• The sum of the array elements before and after modification should be S.

• Negative values ​​are not allowed in the modified array.

• If the array is modified, the minimum value of the array needs to be maximized.

• You can modify an array by adding or subtracting any element of the array.

Using these constraints, we need to find the new array and return the maximum value of the smallest element in the array.

Let us take an example to understand this problem,

Input : arr[] = {4, 5, 6} S = 2
Output : 4

Explanation

The modified array is {4, 5, 5}

Solution

We need to maximize the minimum value of the modified array. We will use a binary search to find the best value for the minimum that is between 0 (minimum possible) and arr_min (maximum possible of). We will check the difference to get the smallest possible value.

Some special conditions,

If S is greater than the sum of the array, there is no solution possible.

If S is equal to the sum of the array, 0 will be the value of the smallest element.

Example

Program illustrating how our solution works

#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S){
   int minVal = a[0];
   int arrSum = a[0];
   for (int i = 1; i < n; i++) {
      arrSum += a[i];
      minVal = min(a[i], minVal);
   }
   if (arrSum < S)
      return -1;
   if (arrSum == S)
      return 0;
   int s = 0;
   int e = minVal;
   int ans;
   while (s <= e) {
      int mid = (s + e) / 2;
      if (arrSum - (mid * n) >= S) {
         ans = mid;
         s = mid + 1;
      }
      else
         e = mid - 1;
   }
   return ans;
}
int main(){
   int a[] = { 4, 5, 6 };
   int S = 2;
   int n = sizeof(a) / sizeof(a[0]);
   cout<<"The maximum value of minimum element of the modified array is "<<findmaximisedMin(a, n, S);
   return 0;
}

Output

The maximum value of minimum element of the modified array is 4

The above is the detailed content of Find the maximum possible value of the minimum value of a modified array in C++. For more information, please follow other related articles on the PHP Chinese website!