Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – min steps to make all elements equal to each other

Here is the detail:

Eg: [1,1,2,4] (init) -> gen1 [2,1,2,4] -> gen2 [4,1,2,4] -> gen3 [4,2,2,4] -> gen4 [4,4,2,4] -> gen5 (no change) -> gen6 [4,4,4,4]

each generation:
odd step: +1 or zero
even step: +2 or zero

in order for all eles to be equaled each other, we need min 6 gens (example). Write an algo to solve this.

Here is one of the comments, I feel puzzled.

we want to fill each slot(odd and even generation) greedily with 1 and 2 alternatively until it crosses the total difference.
In other words, we need an equal number of 1 and 2.
If we need n number of 1 and n number of 2, 1 n + 2 n = total_difference or n = total_difference / 3.
so we need 2n generation.
additionally, we need 1 more generation if total_diff – 3n == 1 or
we need 2 more generation if total_diff – 3*n == 2.
total difference is sum of (max(arr) – arr[i]) for i 0 to len(arr) – 1.

we want to fill each slot(odd and even generation) greedily with 1 and 2 alternatively until it crosses the total difference.

I understand:
In other words, we need an equal number of 1 and 2.

I don’t understand:
If we need n number of 1 and n number of 2, 1 n + 2 n = total_difference or n = total_difference / 3.

I understand
so we need 2n generation.

I don’t understand
additionally, we need 1 more generation if total_diff – 3n == 1 or
we need 2 more generation if total_diff – 3*n == 2.

I don’t understand

// Here is one of solutions from comments and looks like working based on the comment above.
// * g: [1, 2, 2, 4]
const ans = (arr) => {
    const eachCycleVal = 1 + 2; /*cycle contains decreasing 1 followed by 2*/
    const maxVal = Math.max(...arr);
    let totalCycles = 0;
    for (let i = 0; i < arr.length; i++) {
        arr[i] = maxVal - arr[i];
        arr[i] = Math.ceil(arr[i] / eachCycleVal);
        totalCycles += arr[i];
    }
    return 2 * totalCycles;
}

const arr = [1, 2, 2, 4]; // 6
const out = ans(arr);
console.log(out)

original from https://leetcode.com/discuss/interview-question/5798402/Amazon-OA-questions

Tags:

2

Answers


  1. 0

    You could calculate the cycles with this formula:

    s = sum over all items
n = number of items        
d = n * 4 - s                  // missing sum
c = floor(d / 3) * 2 + d % 3

    c is based of the series of 1 2 1 2 1 2 and so on and two pairs from start has the sum of three. to get this pairs, divide by three (take the integer value) and multiply by 2 for all pairs of 1 and 2.

    Finally add the rest value. If it is 1, add one and if it is 2, then the next step is void and the following step needs to add 2 to the item.

    Login or Signup to reply.
  2. 0

    Here is my attempt to solve this:

    The progress is always in this format for the maximum length each step:

    plus 1, plus 2, plus 1, plus 2,...

    Group up 2 steps each:

    (plus 1, plus 2), (plus 1, plus2), ...

    If we see 2 steps as one it would be

    (plus 3), (plus 3), ..., (last 2 steps to reach the goal)

    So we only need to find the last 2 steps
    There are only 3 cases:

    • The last 2 steps are plus 1, plus 2 => 0 extra step(s) needed
    • The last 2 steps are plus 1, plus 0 => 1 extra step(s) needed
    • The last 2 steps are plus 0, plus 2 => 2 extra step(s) needed
    function minDifference(arr) {
    const max = Math.max(...arr)
    const totalDiff = arr.reduce((acc, next) => acc += max - next, 0)
    switch (totalDiff % 3) {
        case 0:
            return 2 * (totalDiff / 3)
        case 1:
            return 2 * Math.floor(totalDiff / 3) + 1
        case 2:
            return 2 * Math.floor(totalDiff / 3) + 2
    }
}
const arr1 = [1, 1, 2, 4] //6
const arr2 = [2, 2, 4] //3
const arr3 = [1, 2, 4] //4
console.log(minDifference(arr1))
console.log(minDifference(arr2))
console.log(minDifference(arr3))
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search