 # Minimize Difference

This question was asked in InterviewBit Academy Enterance Test on 16 Feb.

Given an array of integer A of size N. Minimize the absolute difference between maximum and minimum element of the array.

You can perform two types of operations atmost B times in total to change the values in the array. Multiple operations can be performend on the same element.

1. Increment : A[i] \rightarrow A[i] + 1
2. Decrement : A[i] \rightarrow A[i] - 1

Return the minimum difference possible.

Constraints
1 \leq N \leq 10^{5}
1 \leq A[i] \leq 10^{6}
1 \leq B \leq 10^{9}

Help. How to approach.

1 Like

using binary search.

2 Likes

Can you bit elaborate…

int Solution::solve(vector &A, int B) {

int i, j;
int n = A.size();

int dp = {0};
int mi = INT_MAX;
int ma = INT_MIN;

for(i = 0; i < n; i++){
dp[A[i]]++;
if(A[i] < mi){
mi = A[i];
}
if(A[i] > ma){
ma = A[i];
}
}

i = mi;
j = ma;
int ans = j-i;
int freqMin = dp[i];
int freqMax = dp[j];
while(i < j){

if(B < min(freqMin, freqMax)){
break;
}
if(freqMin < freqMax){
B -= freqMin;
freqMin += dp[i+1];
i++;
}
else{
B -= freqMax;
freqMax += dp[j-1];
j--;
}
ans = j-i;
}
return ans;


}

same as this question on codeforces
https://codeforces.com/contest/1244/problem/E
binary serach + observation

1 Like