Minimum transfer to make array equal

Question

This question is asked in the interview. I am still not able to find what should be right approach to attempt this problem.

Given an array = [7,2,2] find the minimum number of transfer required to make array elements almost equal. If this is not possible the larger elements should come to the left side.

In above example the final state of array would be [4,4,3] and the answer will be 2+ 1 =3. We are transfering 2 from 7 to first 2 and then we are transfering another 1 from 7 to 2.

If the input is [2,2,7] then the answer will be 4 since we need to keep bigger elements on the left side. final state = [4,4,3] 2 transfered from 7 to both 2 to make the final count as 4.

Answer 1

The solution is to imagine what the target array will be. This target array will depend only on the sum of the values in the original array, and the length of the array (which obviously must remain the same).

If the sum of the values is a multiple of the array length, then in the target array all values will be the same. If however there is a remainder, that remainder represents the number of array values that will be one more than some of the value(s) at the end of the array.

We don't actually have to store that target array. It is implicitly defined by the quotient and the remainder of the division of the sum by the array length.

The output of the function is the sum of differences with the actual input array value and the expected value at any array index. We should only count positive differences (i.e. transfers out of a value) as otherwise we would count transfers twice -- once on the outgoing side and again on the incoming side.

Here is an implementation in basic JavaScript:

function solve(arr) {
    // Sum all array values
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
    }

    // Get the integer quotient and remainder
    let quotient = Math.floor(sum / arr.length);
    let remainder = sum % arr.length;

    // Determine the target value until the remainder is completely consumed:        
    let expected = quotient + 1;

    // Collect all the positive differences with the expected value
    let result = 0;
    for (let i = 0; i < arr.length; i++) {
       // If we have consumed the remainder, reduce the expected value
       if (i == remainder) {
           expected = quotient;
       }
       let transfer = arr[i] - expected;
       // Only account for positive transfers to avoid double counting
       if (transfer > 0) {
           result += transfer;
       }
    }
    
    return result;
}

let array = [7,2,2];
console.log(solve(array)); // 6