6

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?

closed as off-topic by Robert Harvey Aug 22 at 3:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking for assistance in explaining, writing or debugging code, or using coding tools, are off-topic here. These can be asked on Stack Overflow if they include the desired behavior, a specific problem or error, and a Minimal, Reproducible Example of the problem." – Robert Harvey
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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
0

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.

0

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. – Peter Feb 6 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. – Kamil Drakari Feb 7 at 17:40
0

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);

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