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