Maximize minimum element of an Array using operations
Last Updated :
31 Aug, 2023
Given an array A[] of N integers and two integers X and Y (X ≤ Y), the task is to find the maximum possible value of the minimum element in an array A[] of N integers by adding X to one element and subtracting Y from another element any number of times, where X ≤ Y.
Examples:
Input: N= 3, A[] = {1, 5, 9}, X = 2, Y = 2
Output: 5
Explanation: We will perform the operation twice as follows:
- Add X to first element and subtract Y from third element. Array becomes – {3, 5, 7}
- Again, add X to first element and subtract Y from third element. Array becomes – {5, 5, 5}
The minimum element is 5. It can be checked that after performing operation with any other indices or any more number of times, the minimum element cannot be made greater than 5.
Input: N = 3, A[] = {11, 1, 2}, X = 2, Y = 3
Output: 3
Explanation: We will perform the operation twice as follows:
- Add X to second element and subtract Y from first element. Array becomes – {8, 3, 2}
- Add X to third element and subtract Y from first element. Array becomes – {5, 3, 4}
The minimum element is 3. It can be checked that after performing operation with any other indices or any more number of times, the minimum element cannot be made greater than 3.
Approach: To solve the problem follow the below idea:
The idea is to use binary search. Initialize two variables lo and hi to the minimum and maximum element of the array, respectively. Now, calculate mid value between lo and hi using binary search. Iterate the array to count the number of additions and subtractions required to make all elements either greater than or equal to mid, using X and Y respectively. If the total number of subtractions required is greater than or equal to the total number of additions required, the update lo=mid and continues the binary search, else update hi=mid-1 and continue the search. When lo and hi become equal, return this value as the answer.
Below are the steps for the above approach:
- Initialize the lower bound (say “lo”) and upper bound(say “hi”) for binary search with minimum and maximum elements of the array respectively.
- In each iteration of the binary search, initialize two variables, say “add” and “subtract” with 0.
- Iterate through the array.
- If the current element of the array is greater than or equal to mid, add (A[i]-mid)/Y to “subtract”.
- Else, add (mid-A[i]+X-1)/X to “add”.
- If “subtract” is greater than or equal to “add”, set lo=mid.
- Else, set hi=mid-1.
- When lo becomes greater than or equal to hi, return lo.
Below is the code for the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
int maximizeMinimumElement(int N, int A[], int X, int Y)
{
int lo = *min_element(A, A + N);
int hi = *max_element(A, A + N);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
int add = 0, subtract = 0;
for (int i = 0; i < N; i++) {
if (mid <= A[i]) {
subtract += (A[i] - mid) / Y;
}
else {
add += (mid - A[i] + X - 1) / X;
}
}
if (subtract >= add) {
lo = mid;
}
else {
hi = mid - 1;
}
}
return lo;
}
int32_t main()
{
int N = 3, X = 2, Y = 2;
int A[] = { 1, 5, 9 };
cout << maximizeMinimumElement(N, A, X, Y);
return 0;
}
|
Java
import java.util.*;
class GFG {
public static int maximizeMinimumElement(int N, int A[],
int X, int Y)
{
int lo = Arrays.stream(A).min().getAsInt();
int hi = Arrays.stream(A).max().getAsInt();
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
int add = 0, subtract = 0;
for (int i = 0; i < N; i++) {
if (mid <= A[i]) {
subtract += (A[i] - mid) / Y;
}
else {
add += (mid - A[i] + X - 1) / X;
}
}
if (subtract >= add) {
lo = mid;
}
else {
hi = mid - 1;
}
}
return lo;
}
public static void main(String[] args)
{
int N = 3, X = 2, Y = 2;
int A[] = { 1, 5, 9 };
System.out.println(
maximizeMinimumElement(N, A, X, Y));
}
}
|
Python3
def maximizeMinimumElement(N, A, X, Y):
lo = min(A)
hi = max(A)
while lo < hi:
mid = lo + (hi - lo + 1) // 2
add = 0
subtract = 0
for i in range(N):
if mid <= A[i]:
subtract += (A[i] - mid) // Y
else:
add += (mid - A[i] + X - 1) // X
if subtract >= add:
lo = mid
else:
hi = mid - 1
return lo
N = 3
X = 2
Y = 2
A = [1, 5, 9]
print(maximizeMinimumElement(N, A, X, Y))
|
C#
using System;
class GFG
{
static int MaximizeMinimumElement(int N, int[] A, int X, int Y)
{
int lo = A[0];
int hi = A[0];
for (int i = 1; i < N; i++)
{
lo = Math.Min(lo, A[i]);
hi = Math.Max(hi, A[i]);
}
while (lo < hi)
{
int mid = lo + (hi - lo + 1) / 2;
int add = 0;
int subtract = 0;
for (int i = 0; i < N; i++)
{
if (mid <= A[i])
{
subtract += (A[i] - mid) / Y;
}
else
{
add += (mid - A[i] + X - 1) / X;
}
}
if (subtract >= add)
{
lo = mid;
}
else
{
hi = mid - 1;
}
}
return lo;
}
static void Main(string[] args)
{
int N = 3;
int X = 2;
int Y = 2;
int[] A = new int[] { 1, 5, 9 };
Console.WriteLine(MaximizeMinimumElement(N, A, X, Y));
}
}
|
Javascript
function maximizeMinimumElement(N, A, X, Y) {
let lo = Math.min(...A);
let hi = Math.max(...A);
while (lo < hi) {
let mid = lo + Math.floor((hi - lo + 1) / 2);
let add = 0;
let subtract = 0;
for (let i = 0; i < N; i++) {
if (mid <= A[i]) {
subtract += Math.floor((A[i] - mid) / Y);
}
else {
add += Math.floor((mid - A[i] + X - 1) / X);
}
}
if (subtract >= add) {
lo = mid;
}
else {
hi = mid - 1;
}
}
return lo;
}
let N = 3;
let X = 2;
let Y = 2;
let A = [1, 5, 9];
console.log(maximizeMinimumElement(N, A, X, Y));
|
Time Complexity: O(N*logN)
Auxiliary Space: O(1)