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.

CodePudding user response：

The minimum amount of transfers done 1 unit at a time is half the total amount by which the input differs from the desired array. "Almost equal" doesn't seem to mean any complication according to what you've given.

CodePudding user response：

This answer is wrong. I just realized after I tried a third example where it didn't work at all (3, 5, 4).

This could help you though, that's why I still post it.

---

This is how I would approach this (I haven't thouroughly tested it).

Consider the array is of length n.

Step 1 : Sort the array descending order

[2, 2, 7] Becomes [7, 2, 2]

Step 2 : Count the displacements

How many numbers are not at their place ? (Stable sort or not stable, we don't care)

[2, 2, 7]

[7, 2, 2]

Here, two numbers are not in their place. We can swap them both in one step, so we need 2 / 2 = 1 more transfer

Step 3 : Compute the sum

Compute the sum of the array. Say k is that sum

Step 4 : Compute the mean and the modulus

mean = k / n. In our case, the mean is 3

mod = k % n. In our case, the modulus is 2

Step 5 : Initialize the new array

The array returned will be of length n.

Initialize it with the mean like this

[3, 3, 3]

Step 6 : Distribute the modulus left to right

Mod = 2, distribute two from left to right. Give one to each.

[3, 3, 3] => [4, 4, 3]

Now, for each number of [7, 2, 2] different than [4, 4, 3], add one transfer.

In our case, all numbers are different, so add 3 to the transfers.

Finally, we have 3 1 = 4 transfers.

CodePudding user response：

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

CodePudding user response：

Let's start form target array. What is it?

Having {7, 2, 2} we want to obtain {4, 4, 3}. So every item is at least 3 and some top items are 3 1 == 4. The algorithm is

let sum = sum(original)
let rem = sum(original) % length(original)  # here % stands for remainder

target[i] = sum / length(original)   (i < rem ? 1 : 0) 

Having original and target

original: 7 2 2
target:   4 4 3
transfer: 3 2 1 (6 in total)

note, that

1. transfer[i] is just an absolute difference: abs(original[i] - target[i])
2. we count each transfer twice: once we subtract and then we add.

So the answer is

sum(transfer[i]) / 2 == sum(abs(original[i] - target[i])) / 2 

Code (c#):

private static int Solve(int[] initial) {
  // Don't forget about degenerated cases
  if (initial is null || initial.Length <= 0)
    return 0;  

  int sum = initial.Sum();
  int rem = sum % initial.Length;

  int result = 0;

  for (int i = 0; i < initial.Length;   i) 
    result  = Math.Abs(sum / initial.Length   ((i < rem) ? 1 : 0) - initial[i]);
  
  return result / 2;  
}

Demo: (Fiddle)

    int[][] tests = new int[][] {
        new int[] {7, 2, 2},
        new int[] {2, 2, 7},
        new int[] {},
        new int[] {2, 2, 2},
        new int[] {1, 2, 3},
    };
    
    string report = string.Join(Environment.NewLine, tests
      .Select(test => $"[{string.Join(", ", test)}] => {Solve(test)}"));
    
    Console.Write(report);

Outcome:

[7, 2, 2] => 3
[2, 2, 7] => 4
[] => 0
[2, 2, 2] => 0
[1, 2, 3] => 1

CodePudding user response：

Seems to me like a simple problem that can be solved with greedy approach.

Steps:

1. Sum up the input array-elements S, divide by its length n. Lets say, the quotient is Q and remainder (mod) is R. Then, final array target will have 1st R elements with value = Q 1. Rest of the elements will be Q.
2. Number of transfers will be half of the sum of absolute difference at each (corresponding) position in input and target arrays.

Example:

Input [7, 2, 2]
S=13 n=3 Q=11/3=3 R=11%3=2
Target [3 1, 3 1, 3]
Answer = (abs(7-4)   abs(2-4)   abs(2-3)) / 2 = 3