Make two array sum same with limited values

Question

I have two arrays A & B (size of the array is 1 to 100,000) that can take values only 1,2,3,4,5,6.

Now my task is to make minimum numbers to be changed in arrays such that the sum of both the arrays is the same.

Example 2:

A=[5,4,1,2,6,6] & B=[2], we have to make A as [1,1,1,1,1,1] so we have to change A 5 times and then B=[6] once, so function should return 6.

Example 3:

A=[1,2,3,4,3,2,1] and B[6], function should return -1.

Method signature looks like this.

public int task(int[] A, int[] B) {
   int diff = Math.abs(A.length - B.length);
   if(diff >=6) return -1;

   // 
}

I am able to get answer for example 3 with simple condition. Bit not for first 2 examples.

What approach should I follow to solve this program? As we can turn each and every element in A & B and do a comparison, but that is more complex.

Answer 1

The alghorithm can be as following:

Prepare data part

Go through all items in array A and B and find out how many of each number (1,2,3,4,5,6) is in each array. Preferable have 2d array that stores the indexes of those numbers, so you can easily access it later.

i.e. array A=[1,1,1,4,6,4] will be translated into new 2d array as

2darr=
[]
[0,1,2]
[]
[]
[3,5]
[]
[4]

so when you i.e. want to see how many 1 are there you can see that 2darr[1].length is 3. And when you want to find out where it is i.e. the 2darr[1][0] will get you index in source array and A[0] is indeed 1

In process you can also count the sum, but even without it, the sum now can be easily found out just going through lengths of each subarray in 2darray.

Alghoritm

To find the minimum amount of changes, you will first find out which sum is smaller and which bigger. Then the best change is to start changing 1 values to 6 in smaller array or changing 6 values to 1 in bigger arrays. Then 2 to 6 in smaller array and 5 to 1 in bigger array. And then continue with other numbers.

In process you can changing the arrays based on indexes you already have and do it as long as needed to get both arrays to same sum. This is detailed alghoritm that will show you how actually both arrays will look like to satisfy your needs. Its O(n), so there is definitely no way how to make it faster as you have to go through all fields just to get the sum.

I suggest to do it so you can see the actual result. On the other hand, if you think more deeply, it can be done more easily, if you just seek the right answer - you just need to know how many times each number in each array is and then just find out how many changes are needed just by simple math. You already know, you are just changing up to all 1 to 6 in smaller array and up to all 6 to 1 in bigger array and it can be just counted easily how many of them you need to change and if it is sufficient or you change all of them and then you will continue with 5 to 1 and 2 to 6 etc.

Example

Imagine that A.length is 500 and B.length is 300. The sum of A=1000and B=700. You find out that A has 30 repetitions of number 6 and B has 20 repetitions of number 1. In A you change all those 6 to 1, therefore reducing it by 30*5=150 to total of A=850 and in B you change all those 1 to 6 and increasing the value 20*5=100 and therefore B=800. You did 50 changes in total.

Then you continue with higher number in smaller array and with lower number in bigger array. You find out that A has 100 numbers of 5. Reducing 5 to 1 decreases value by 4 for each. Right now you have only 50 value difference. 50/4=12.5, therefore you need to change 13 numbers and you are done. The answer is that minimum amount of changes is 63.

Answer 2

The impossibility-criteria is a simple one as you suspect, but it is different from what you guess: it depends on the length of the arrays, which determines their minimal and maximal sums. The shorter array can not produce a sum which is greater than 6 times its length (all elements are 6s) and the longer array can not produce a sum which is less than its length (all elements are 1s):

if( Math.min(A.length, B.length) * 6 < Math.max(A.length ,B.length) )
  return -1;

Then you need the sums and the statistics what the other answer describes, but maybe there is place for a slightly different explanation. In order to have the two sums meet, the smaller one can be increased and the larger one can be decreased. For having the minimum amount of steps, you always want to make the largest steps possible, via starting to replace 1s with 6s in the smaller sum (each replacement increasing the sum by 5) and 6s with 1s in the larger sum (each replacement decreasing it by 5), and so on.

As you do not want to generate the steps (at least to my understanding), actually you can track the difference only and also count the pairs together (6s in the larger-sum-array and 1s in the smaller-sum-array, then the same with 5-2, etc.). And in fact you can do this pairing even at the beginning, without knowing which one is the larger/smaller sum, because the pairs will stay pairs, just their direction changes.

Example is JavaScript so it can run here, but I try to write it as Java as possible:

function task(A,B){
  if( Math.min(A.length, B.length) * 6 < Math.max(A.length, B.length) )
    return -1;
    
  var diff=0;
  var statistics=[0,0,0,0,0,0]; // would be a new int[6] in Java
  for(var item of A){ // for(int item : A) in Java
    // this loop guesses that A has the larger sum
    diff+=item;
    statistics[item-1]++; // 1s are counted in [0], 2s in [1], ... 6s in [5]
  }
  for(var item of B){ // for(int item : B) in Java
    // this loop guesses that B has the smaller sum
    diff-=item;
    statistics[6-item]++; // 1s are counted in [5], 2s in [4], ... 6s in [0]
  }
  if(diff<0){
    // the guess was wrong, swaps are needed
    diff=-diff;
    for(var i=0;i<3;i++){
      var swap=statistics[i];
      statistics[i]=statistics[5-i];
      statistics[5-i]=swap;
    }
  }
  
  var log=[A.join()," ",B.join()," ",diff," ",statistics.join()].join(); // <-- this one...
  
  // at this point
  // - array indices are conveniently denoting step sizes
  // - diff is non-negative
  // - and we know there is a solution (so we won't run out of array indices for example)
  var changes=0;
  var i=5;
  while(diff>0){
    var step = Math.min(statistics[i], Math.ceil(diff/i));
    // would better be "int step = Math.min(statistics[i], (diff+i-1)/i);" in Java
    // as Math.ceil() produces a double
    changes += step;
    diff -= i*step;
    i--;
  }
  return [changes," ",log].join();                                       // <-- ... and this
                                                                         // are only visuals
  return changes;
}

console.log(task([1,2,3,4,3,2,1],[6]));
console.log(task([6],[1,2,3,4,3,2,1]));
console.log(task([2,3,1,1,2],[5,4,6]));
console.log(task([5,4,6],[2,3,1,1,2]));
console.log(task([5,4,1,2,6,6],[2]));
console.log(task([2],[5,4,1,2,6,6]));

At the end I've just thrown it together in Java too: https://ideone.com/mP3Sel