667. Doubling Neighbours Then Settling the Zeros
Apply this to the array ONCE, left to right: for each position i from the first to the
second last, if a[i] is not zero and equals a[i+1], double a[i] and set a[i+1] to zero.
Then move every zero to the END, keeping the order of the non-zero values.
1 2 2 1 1 0 -> 1 4 2 0 0 0
4 4 0 4 -> 8 4 0 0
1 2 3 4 -> 1 2 3 4
## The pass is strictly left to right, and once
After position i is handled, position i+1 may have become zero. The next step still looks at
i+1 against i+2, and since a[i+1] is now zero the rule does not fire, because the rule
requires a non-zero value.
That is why a single forward pass is enough and why the zero test is part of the condition.
1 1 1 gives 2 1 0, not 2 2 or 4: the first two combine, and the third has nothing left
to combine with.
## Then the write pointer
Moving the zeros is the read-and-write sweep from problem 622, with the survivors being the non-zero values:
w = 0
for r in 0 .. n-1:
if a[r] != 0: a[w] = a[r]; w += 1
fill a[w .. n-1] with 0
The writer never overtakes the reader, so writing into the same array is safe.
## Why the two phases must not be merged
It is tempting to compact while doubling. Doing so changes which values are adjacent partway
through, and the rule is defined on the ORIGINAL adjacency. 4 4 0 4 gives 8 4 0 0: the two
fours combine, and the last four is not dragged into them even though compacting would have
made it adjacent.
That input is the test, and it is what separates a correct two-phase solution from a merged one.
## Boundaries
An array with no zeros and no equal neighbours is unchanged. An array of all zeros is unchanged.
## Overflow
A value doubles at most once, so an input of 10^9 becomes 2 * 10^9. Check that
against the limit rather than assuming: a signed 32 bit integer holds up to 2147483647,
so 2000000000 FITS, with about seven percent to spare. This problem has no overflow.
It is close enough to the edge to deserve the arithmetic rather than a glance. An input cap
of 1.1 * 10^9 instead of 10^9 would put the doubled value over the limit, and nothing
about the shape of the problem would have changed to warn you.
## Cost
Time O(n) in two passes. Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n non-negative integers.
Output
Print the n resulting values on one line, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.