# Minimum steps to make all elements equal [closed]

Given an array A of N positive integers (N <= 20), we have the following operation. For any two consecutive non-equal elements, we can replace the larger number by the absolute value of the difference between these two numbers. We keep using this operation until all elements are equal. Find a way to make all elements are equal with a minimum number of steps (number of operations as described)

For example, A = 9, 6, 15, 12. The minimum number of steps is 5 (correct by Pieter B).

``````9 6 9 12
9 6 9 3
9 6 3 3
3 6 3 3
3 3 3 3
``````

I'm thinking at each step, we can choose the largest element and replace it with the difference with its smaller neighbor. However, it fails for the test 1, 3, 2. It also fails if we choose to replace the largest element with the difference with its larger neighbor; for example, 3, 8, 4.

Is there any way to do this problem except brute force? If I'm using brute force, is replacing the largest element the right choice?

• "If I'm using brute force, is replacing the largest element the right choice?" No, but only as that would no longer be brute force. Brute force would necessarily try all possible solution paths, not just the ones favoring largest element. Commented Feb 16, 2017 at 23:00
• Thank you. I tried to narrow down the search space. I think it's reasonable to choose the largest element at each step. Do we have a better way to do it?
– dh16
Commented Feb 16, 2017 at 23:12
• just to clarify, what is your task? to create 1) an optimal algorithm solving each case in the simplest way stright away, or is ot to 2) create an algorithm that for given data set will find which is the best way of solving it (testing many ways)?
– rsm
Commented Feb 17, 2017 at 0:22
• I think it should be #1. The input data is unknown, only knowing that there are no more than 20 elements.
– dh16
Commented Feb 17, 2017 at 3:28
• What you're basically describing is en.wikipedia.org/wiki/Euclidean_algorithm Commented Feb 17, 2017 at 8:18

Actually, can do this as fork/ join problem. In your example, you're proceeding iteratively. You may want to try splitting the data recursively, reducing each part, the performing a join operation between the parts. Your previous example can be solved:

`9 6 - 3 12`

`3 6 - 3 12`

`3 6 - 3 9`

`3 3 - 3 9`

`3 3 - 3 6`

`3 3 - 3 3`

Which isn't any better.

While this won't always have fewer "steps", if you can perform steps in parallel, it can be much more efficient. If we have two threads, so that we can do two comparisons at a time, we get:

`9 6 - 3 12`

`3 6 - 3 9`

`3 3 - 3 6`

`3 3 - 3 3`

As the problem space becomes larger, and/or we gain more "threads" this solution becomes more efficient.

With your small problem space (20 max), an actual implementation would probably have too much overhead to beat the iterative case, time wise.

Which leaves us wondering, "What exactly is a step? (Apologies for poor formatting)

• Thank you. Sorry for a confusion about "steps". What I meant was to minimize the number of operations that being used, so if we proceed in parallel, the number of operations doesn't change. If the input contains only 2 numbers: 1, 10^9, I think we have to do it ~10^9 times. Is brute force the only way to do it?
– dh16
Commented Feb 17, 2017 at 7:21

I'd say at each step you could calculate the average of the sequence and do a replacement that would give a new value close to that. If all of the values turned out to be the same, you could then change the left-most (or rightmost) digit.

If you want the minimum amount of operation on the array you can do the following:

Pick the largest and the smaller second largest element from the array and overwrite the largest with the difference.

Quick implementation in js:

``````const allEqual = arr => arr.every(val => val === arr[0]);

let a = [9,6,15,12];

let i = -1;
while (!allEqual(a) && i++< 100) {
console.log(a);
let largest = -1;
let secondLargest = -1;

for (let j in a) {
if (a[j] > (a[largest] | 0)) {
secondLargest = largest;
largest = j;
} else if (a[j] > (a[secondLargest] | 0) && a[j] < (a[largest] | 0)) {
secondLargest = j;
}
}
a[largest] = a[largest] - a[secondLargest];
}
console.log(a);
console.log(i);
``````
• Maybe I shouldn't post code here, but I think it more clear this way than my explanation with my lack of English. Commented Feb 6, 2019 at 22:05
• I think you've made a mistake. The operation permitted only allows replacing an element with the absolute difference between it and one of its adjacent elements, not any other element. Commented Feb 7, 2019 at 17:40

Herewith I've done the solution in JavaScript in traditional manner so that you can easily understand and convert it into another one.

``````let arr = [9, 6, 15, 12],
arrLength = arr.length,
count = 0,
flagToBegin = 0;

let iterateForReplaceMax = function(arr) {
flagToBegin = diffAt(arr);
while(flagToBegin >= 0) {
replaceMax(arr);
}

console.log("total count: ",count);
console.log("final array: ",arr.toString());
return arr;
}

let replaceMax = function(arr) {
count++;
console.log("current count= ",count);
for(i=flagToBegin; i< arrLength-1; i++){
if(arr[i+1]) {
if(arr[i] < arr[i+1]) {
arr[i+1] = arr[i];
} else if(arr[i] > arr[i+1]) {
arr[i] = arr[i+1];
}
}
}
console.log("11 array: ",arr.toString());
flagToBegin = diffAt(arr);
}

let diffAt = function(array) {
for(let i=0; i< array.length-1; i++) {
if(array[0] !== array[i+1]) {
return i;
}
}
return -1;
}

iterateForReplaceMax(arr);
``````