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[1000010] = {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