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?