I am trying to design an algorithm for a challenge that I found in this discussion on LeetCode, and which can be phrased as follows:
Given is an array with integers, such as [1,1,2,4]. The goal is to make all values in this array equal by repeatedly adding 1 or 2 to a freely selected value, with following rules:
An operation on this array turns it into a next "generation". The given array is generation 0. Next generations are numbered 1, 2, 3, ... If the next generation has an odd sequence number, you may add 1 to one selected value. To produce the next even generation you may add 2 to one selected value. In either case you may also choose to pass and just take the unchanged array to become the next generation.
Return the minimum number of generations (after the initial state) to reach the goal.
Example:
Input: [1,1,2,4]
Expected output: 6
Explanation:
- Generation 1: [2,1,2,4]
- Generation 2: [4,1,2,4]
- Generation 3: [4,2,2,4]
- Generation 4: [4,4,2,4]
- Generation 5: (no change)
- Generation 6: [4,4,4,4]
In order for all values to equal each other, we need a minimum of 6 generations.
LeetCode user @SOLA89 commented as follows:
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.
This is the code that another commenter @You_can provided, which I converted to JS:
// * 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)
The quoted reasoning and program seem to apply the same algorithm, and intuitively it seemed correct, but now I found it fails for input [2, 2, 4]. The algorithm leads to output 4, but it can be done with 3 generations.
What is the correct algorithm to solve this?
The greedy approach is not always correct. If we are at an odd generation, and there is just one number left that is not equal to the maximum, and it is 2 less, then we shouldn't add 1 to it, but do nothing in this generation.
Also, the claim that we can derive the number of needed generations from the total difference alone is not correct. It matters how the values are distributed. For instance, the total difference is the same (3) for these two inputs:
[0, 3]
[0, 0, 0, 1]
But the needed generations are different. In the first case we just need two generations (add 1, add 2). In the second we cannot do anything in the "even" generations, so we need 5 generations.
First we should identify how far each value is from the maximum value. Then we could reason that for the odd distances we certainly need at least one odd generation to make that distance even. So we have a lower bound for the number of odd generations. Call that number odd. For all the even distances that remain we could first assume that they are all covered by even generations where we take units of 2. Call that number of even generations even. The invariant is that 2*even+odd equals the sum of the distances to the maximum value.
Whichever is the greatest (odd or even) determines the total number of generations. More precisely the number of generations needed is now max(odd, even) * 2 - (odd > even). The factor 2 reflects that we have an odd+even generation pair. The subtraction reflects that if we have more odd generations, we don't need an even generation to follow the last odd one, so there we don't have a pair, but just the odd generation.
Ideally we would want odd==even or odd==even+1, because then we can alternate between odd and even generations without ever needing a wasteful generation where we cannot do anything.
If it turns out that odd > even+1, there is nothing much we can do, and we will have to spend some even generations on doing nothing.
If odd < even we would have odd generations where we do nothing. But in that case we could recategorise a two as two indidvidual odd, so that we could use 2 more odd generations and one less even generation. How many times we could do this, depends on how much less odd is than even. While odd + 2 <= even we can perform this operation, which reduces even by 1, and increases odd by 2. This could make odd equal or one more than even, and that is an ideal situation (no wasted generation!). Or, it could be that odd + 1 == even, which is less ideal, as you would have one empty odd geneartion, but it is the best we can hope for. This means we should apply this "split" of even into two odds a number of times that is floor((even - odd + 1) / 3).
Here is an implementation with comments:
function solve(arr) {
const maxVal = Math.max(...arr);
let odd = 0, even = 0;
for (let val of arr) {
val = maxVal - val;
// If the distance is odd, we need at least
// one odd generation for this value:
odd += val % 2;
// ... and we need at most this number of even generations:
even += Math.floor(val / 2);
}
// We aim to have odd == even or odd == even + 1.
// Because then we don't waste a generation doing nothing.
// We cannot do anything about the case where odd > even + 1,
// but we *can* often do something when odd < even: in that case
// we could decide to use pairs of odd generations to
// replace even generations.
if (odd < even) { // We can replace some evens with odd pairs
const splitEven = Math.floor((even - odd + 1) / 3);
odd += splitEven * 2; // Two odd generations can do what one even does
even -= splitEven;
}
// Calculate the number of generations by the type we need the most
// If we have more `odd`, then that will be the type of the last generation
// and so no even will follow it (we subtract one)
return Math.max(odd, even) * 2 - (odd > even);
}
const tests = [
[[0,0,4], 6], // [1,0,4][1,2,4][2,2,4][4,2,4](no-op)[4,4,4]
[[0,1,3,4], 6], // [0,1,4,4][2,1,4,4][2,2,4,4][2,4,4,4](no-op)[4,4,4,4]
[[1,1,1,2], 5],
[[1,1,2,2], 3],
[[2,2,2,4], 4],
[[0,3,3,4], 4], // [0,4,3,4][2,4,3,4][2,4,4,4][4,4,4,4]
[[1,2,2,3], 3],
[[1,1,2,2,4], 7],
[[0,1,2,3,4], 7],
[[0,0,2,3,4], 8], // [0,0,2,4,4][0,0,4,4,4] ...see 6 more for [0,0,4]
[[0,1,3,3,4], 6],
[[1,1,2,2,3,4], 8],
[[0,0,2,2,2,4], 10],
[[0,0,0,3,3,4], 10],
];
for (const [arr, expected] of tests) {
const result = solve(arr);
if (result !== expected) throw `[${arr}]: expected ${expected}, got ${result}`;
}
console.log("tests passed");