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}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def valid(self,arr, n): 

        # code here 

Solutions:
class Solution:

	def valid(self, arr, n):
		stck = list()
		count = 0
		for i in arr:
			if i != 0 and (len(stck) == 0 or stck[-1] != i):
				stck.append(i)
			elif stck and stck[-1] == i:
				stck.pop()
				stck.append(2 * i)
				count += 1
			else:
				count += 1
		zero = [0 for i in range(count)]
		stck.extend(zero)
		return stck


class Solution:

	def valid(self, arr, n):
		ind = 0
		for i in range(1, n):
			if arr[i] != 0 and arr[i] == arr[ind]:
				arr[ind] = arr[ind] * 2
				arr[i] = 0
			elif arr[i] != 0:
				ind = i
		j = 0
		for i in range(n):
			if arr[i] != 0:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		return arr


class Solution:

	def valid(self, arr, n):
		a = []
		c = 0
		for i in arr:
			if i != 0 and (len(a) == 0 or a[-1] != i):
				a.append(i)
			elif len(a) != 0 and a[-1] == i:
				a.pop()
				a.append(2 * i)
				c += 1
			else:
				c += 1
		for i in range(c):
			a.append(0)
		return a


class Solution:

	def valid(self, arr, n):
		zero_count = 0
		stack = []
		for item in arr:
			if item == 0:
				zero_count += 1
			elif stack and stack[-1] == item:
				stack[-1] *= 2
				zero_count += 1
			else:
				stack.append(item)
		return stack + [0] * zero_count


class Solution:

	def valid(self, arr, n):
		ind = 0
		for i in range(n):
			if i == 0 or arr[i] == 0:
				continue
			elif arr[i] == arr[ind]:
				arr[ind] = 2 * arr[ind]
				arr[i] = 0
			else:
				ind = i
		ind = 0
		for i in range(n):
			if arr[i] != 0:
				(arr[ind], arr[i]) = (arr[i], arr[ind])
				ind += 1
		return arr


class Solution:

	def valid(self, a, n):
		prev = 0
		idx = -1
		for i in range(n):
			if a[i] != 0 and a[i] != prev:
				prev = a[i]
				idx = i
			elif a[i] != 0 and a[i] == prev:
				a[i] = 0
				a[idx] = a[idx] * 2
				prev = a[idx]
		start = 0
		i = 0
		while i < n:
			if a[start] == 0:
				a.append(a[start])
				a.remove(a[start])
				i += 1
			else:
				i += 1
				start += 1
		return a


class Solution:

	def valid(self, arr, n):
		res = [0] * n
		res[0] = arr[0]
		prev_indx = 0
		for i in range(1, n):
			if arr[i] == 0:
				continue
			if arr[i] != res[prev_indx]:
				res[i] = arr[i]
				prev_indx = i
			elif arr[i] == res[prev_indx]:
				res[prev_indx] += res[prev_indx]
				res[i] = 0
		non_zero = 0
		for i in range(n):
			if res[i] != 0:
				(res[i], res[non_zero]) = (res[non_zero], res[i])
				non_zero += 1
		return res


class Solution:

	def valid(self, arr, n):
		cur_val = -1
		for x in range(len(arr)):
			if cur_val >= 0:
				if arr[x] == arr[cur_val]:
					arr[cur_val] = arr[cur_val] * 2
					arr[x] = 0
			if arr[x] >= 1:
				cur_val = x
		zero_num = arr.count(0)
		for x in range(zero_num):
			arr.remove(0)
		for x in range(zero_num):
			arr.append(0)
		return arr
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.valid(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def valid(self, arr, n):
		prev = -1
		previ = -1
		count = 0
		i = 0
		while i < n:
			if arr[i] == 0:
				arr.pop(i)
				count += 1
				i = i
				n = n - 1
				continue
			if prev != arr[i] and arr[i] != 0:
				prev = arr[i]
				previ = i
				i += 1
				continue
			if prev == arr[i]:
				arr[previ] = arr[previ] * 2
				arr.pop(i)
				arr.append(0)
				prev = arr[previ]
				i = i
				n = n - 1
				continue
			i += 1
		for i in range(count):
			arr.append(0)
		return arr
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.valid(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def valid(self, arr, n):
		li = []
		count = 0
		for i in range(n):
			if arr[i] != 0:
				li.append(arr[i])
			else:
				count += 1
		if count == n:
			return [0] * n
		i = 0
		j = 1
		while j < len(li):
			if li[i] == li[j]:
				li[i] = 2 * li[i]
				li[j] = 0
				j += 1
			else:
				i = j
				j += 1
		li2 = []
		for i in range(len(li)):
			if li[i] != 0:
				li2.append(li[i])
			else:
				count += 1
		li3 = [0] * count
		li2.extend(li3)
		return li2


class Solution:

	def valid(self, arr, n):
		i = 0
		j = 0
		while i < n - 1:
			if arr[i] == 0:
				i += 1
				continue
			j = i + 1
			while arr[j] == 0 and j < n - 1:
				j += 1
			if arr[i] == arr[j]:
				arr[i] = 2 * arr[i]
				arr[j] = 0
				continue
			else:
				i = j
		j = 0
		i = 0
		for i in range(n):
			if arr[i] != 0:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		return arr


class Solution:

	def valid(self, arr, n):
		stack = []
		for i in range(n):
			if arr[i] > 0 and len(stack) == 0:
				stack.append(arr[i])
			elif arr[i] == 0:
				pass
			elif arr[i] == stack[-1]:
				stack[-1] = 2 * stack[-1]
			else:
				stack.append(arr[i])
		zero = n - len(stack)
		for i in range(zero):
			stack.append(0)
		return stack


class Solution:

	def valid(self, arr, n):
		count = 0
		while 0 in arr:
			count += 1
			arr.remove(0)
		i = 0
		while i < len(arr):
			if i + 1 < len(arr) and arr[i + 1] == arr[i]:
				arr[i] = 2 * arr[i]
				count += 1
				arr.pop(i + 1)
				i -= 1
			i += 1
		for i in range(count):
			arr.append(0)
		return arr


class Solution:

	def valid(self, arr, n):
		l = 0
		r = 1
		tt = []
		ze = 0
		while r < n:
			if arr[l] == 0:
				l = r
				r += 1
			elif arr[r] == 0:
				while r < n and arr[r] == 0:
					r += 1
			elif arr[l] == arr[r]:
				arr[l] *= 2
				arr[r] = 0
				r += 1
			else:
				tt.append(arr[l])
				l = r
				r += 1
		if arr[l] != 0:
			tt.append(arr[l])
		ze = arr.count(0)
		return tt + [0] * ze


class Solution:

	def valid(self, arr, n):
		l = 0
		r = 1
		z = 0
		final = []
		while r < n:
			if arr[l] == 0:
				l = r
				r += 1
			elif arr[r] == 0:
				while r < n and arr[r] == 0:
					r += 1
			elif arr[l] == arr[r]:
				arr[l] *= 2
				arr[r] = 0
				r += 1
			else:
				final.append(arr[l])
				l = r
				r += 1
		if arr[l] != 0:
			final.append(arr[l])
		z = arr.count(0)
		return final + [0] * z