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

binary serach + observation

3 Likes

We can solve this using HashMap without binary search also.

public static int minimizeDif(ArrayList<Integer> A, int B) {
    	int min = Integer.MAX_VALUE;
    	int max= Integer.MIN_VALUE;
    	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    	// find the min and max in the array
    	// Also hash the whole array to find the occurrences of all elements
    	for (int i=0; i<A.size(); i++) {
    		min = Math.min(min, A.get(i));
    		max = Math.max(max, A.get(i));
    		map.put(A.get(i), map.getOrDefault(A.get(i), 0)+1);
    	}
    	// terminating condition if B<=0 can't perform any more ops
    	while (B>0 && min<max) {
    		// if the occurrences of min < if the occurrences of max 
    		// => increase min by 1
    		// else decrease max by 1
    		if (map.getOrDefault(min, 0) < map.getOrDefault(max, 0)) {
    			// check if the occurrences of min element in array is less than the number of available number ops 
    			if (B < map.getOrDefault(min, 0))
    				break;
    			map.put( min+1, map.getOrDefault(min+1, 0) + 
    					map.get(min) );
    			B-= map.get(min);
    			min = min + 1;
    			

    		}
    		else {
    			//check if the occurrences of max element in array is less than the number of available number ops
    			if (B < map.getOrDefault(max, 0))
    				break;
    			map.put( max-1, map.getOrDefault(max-1, 0) +
    					map.get(max) );
    			B-= map.get(max);
    			max = max - 1;
    		}
    	}
    	
    	return max - min;
    }

TC => O(n) + O(range of min and max)
SC => O(n) + O(range of min and max)