7

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?

Thank you.

  • 1
    "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. – Erik Eidt Feb 16 '17 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 Feb 16 '17 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 Feb 17 '17 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 Feb 17 '17 at 3:28
  • What you're basically describing is en.wikipedia.org/wiki/Euclidean_algorithm – Pieter B Feb 17 '17 at 8:18
0

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 Feb 17 '17 at 7:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.