Given an array arr[] of size N containing integers, zero is considered an invalid number, and rest all other numbers are valid. If two nearest valid numbers are equal then double the value of the first one and make the second number as 0. At last move all the valid numbers on the left.
Example 1:
Input: N = 12
arr[] = {2, 4, 5, 0, 0, 5, 4, 8, 6, 0,
6, 8}
Output: 2 4 10 4 8 12 8 0 0 0 0 0
Explanation: After performing above
given operation we get array as,
2 4 10 0 0 0 4 8 12 0 0 8, then shifting
all zero's to the right, we get resultant
array as - 2 4 10 4 8 12 8 0 0 0 0 0
Example 2:
Input: N = 2, arr[] = {0, 0}
Output: 0 0
Explanation: All elements in the array
are invalid .

Your Task:
You don't need to read input or print anything. Complete the function valid() that takes array arr[] and integer N as input parameters and returns the resultant array.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 10^{5}

见题面

见题面