How to compute minimum number of operation required to make all the elements of sequence equal to each other

Question

The problem is from a programming competition.

You are given two sequences A (a1, a2, a3, ... an) and B (b1, b2, b3, ... bn) of the same length N. In each step you can set ai = ai - bi if ai >= bi. Determine the minimum number of steps required to make all the numbers in A equal to each other.

For Example

A = {5, 7, 10, 5, 15} 
B = {2, 2, 1, 3, 5}

In the above example, the minimum number of steps required to make all the elements in A equal to each other is 8.

A = {5, 15, 25, 35, 45, 90, 100}
B = {5, 5, 5, 5, 5, 5, 5}

In the above example, the minimum number of steps required to make all the elements in A equal to each other is 56.

Do note that if it is not possible to make all the elements of the sequence A equal to each other then print -1.

For Example

A = {5, 6}  
B = {4, 3}

In the above case, the answer is -1 because it is impossible to make all the elements of A equal to each other.

A = {5, 15, 25, 35, 45, 90, 100}
B = {5, 5, 5, 5, 5, 0, 5}

In the above case, the answer is -1 because it is impossible to make all the elements of A equal to each other.

Could anyone can help me out on how to solve this problem efficiently?

Answer 1

The target cannot be greater than the smallest element in A. If m is the index of the smallest element in A, the target must also be one of the values A[m] - k * B[m] (non-negative integer k). Since there may be duplicates of the smallest element in A, each with a different b, to simplify, we can just try all targets equal or smaller than min(A).

We try them in a descending loop since clearly the highest valid one would take the least steps to reach. The check for validity, which must apply to all (a, b) pairs, given candidate target t:

(a - t) mod b == 0

Example:

A = {5, 7, 10, 5, 15}
B = {2, 2, 1, 3, 5}

t = 5

a's:

 5: 5 == 5
 7: (7 - 5) mod 2 == 0
10: (10 - 5) mod 1 == 0
 5: 5 == 5
15: (15 - 5) mod 5 == 0

JavaScript code:

function f(A, B){
  const n = A.length;
  const m = Math.min(...A);
  let result;
  
  for (let t=m; t>=0; t--){
    result = 0;
    
    for (let i=0; i<n; i++){
      if ((A[i] - t) % B[i] == 0){
        result = result + (A[i] - t) / B[i];
        
      } else {
        result = -1;
        break;
      }
    }
    
    if (result > -1)
      return result;
  }
  
  return result;
}

var ABs = [
  [[5, 7, 10, 5, 15],
   [2, 2, 1, 3, 5]],

  [[5, 6],
   [4, 3]]
];

for (let [A, B] of ABs){
  console.log(`A: ${ A }`);
  console.log(`B: ${ B }`);
  console.log(f(A, B));
  console.log('');
}