Given a non-negative integer(without leading zeroes) represented as an array A of N digits. Your task is to add 1 to the number (increment the number by 1). The digits are stored such that the most significant digit is at the starting index of the array.
Example 1:
Input:
N = 4
A[] = {5, 6, 7, 8}
Output: 5 6 7 9
Explanation: 5678 + 1 = 5679
Example 2:
Input:
N = 3
A[] = {9, 9, 9}
Output: 1 0 0 0
Explanation: 999 + 1 = 1000
Your Task:
You don't need to read input or print anything. Your task is to complete the function addOne() which takes the array of integers a and n as parameters and returns an list of integers denoting the answer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N) for the list of integers used to store the returning result. 
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ A[i] ≤ 9
There are no leading zeros in the input number.

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N) for the list of integers used to store the returning result.

Starter code:
#User function Template for python3





# function for adding one to number 

class Solution:

    def addOne(self,a, n):

        # code here

Solutions:
class Solution:

	def addOne(self, a, n):
		if a[-1] < 9:
			a[-1] += 1
		else:
			for i in range(len(a), 0, -1):
				if a[i - 1] < 9:
					a[i - 1] += 1
					break
				else:
					a[i - 1] = 0
					if i == 1:
						a.insert(0, 1)
		return a


import sys

class Solution:

	def addOne(self, a, n):
		n = n - 1
		while n >= 0 and a[n] == 9:
			a[n] = 0
			n -= 1
		if n < 0:
			a.insert(0, 1)
		else:
			a[n] = a[n] + 1
		return a


class Solution:

	def addOne(self, a, n):
		if a[-1] != 9:
			a[-1] += 1
			return a
		i = n - 1
		c = 1
		while i >= 0:
			if a[i] == 9 and c:
				a[i] = 0
			else:
				a[i] += 1
				c = 0
				break
			i -= 1
		if c:
			a = [1] + a
		return a


class Solution:

	def addOne(self, arr, n):
		carry = 1
		for i in range(n - 1, -1, -1):
			if carry == 1:
				num = arr[i] + 1
				arr[i] = num % 10
				num = num // 10
				if num == 1:
					carry = 1
				else:
					carry = 0
					break
		if carry == 1:
			arr.insert(0, 1)
		return arr


class Solution:

	def addOne(self, a, n):
		carry = a[-1] == 9
		if not carry:
			a[n - 1] += 1
		index = n - 1
		while carry and index >= 0:
			if a[index] == 9:
				a[index] = 0
			else:
				a[index] += 1
				carry = False
			index -= 1
		if carry:
			a.insert(0, 1)
		return a


class Solution:

	def addOne(self, a, n):
		a = a[::-1]
		carry = 1
		for i in range(n):
			temp = a[i] + carry
			carry = temp // 10
			temp = temp % 10
			a[i] = temp
		if carry != 0:
			a.append(carry)
		a = a[::-1]
		return a


class Solution:

	def addOne(self, a, n):
		i = n - 1
		while True:
			a[i] += 1
			if a[i] == 10:
				a[i] = 0
				i -= 1
				if i == -1:
					a.insert(0, 1)
					break
			else:
				break
		return a


class Solution:

	def addOne(self, a, n):
		index = len(a) - 1
		while index >= 0 and a[index] == 9:
			a[index] = 0
			index -= 1
		if index < 0:
			a.insert(0, 1)
		else:
			a[index] += 1
		return a


class Solution:

	def addOne(self, arr, n):
		carry = 0
		for i in range(n - 1, -1, -1):
			if arr[i] == 9 and i == n - 1:
				arr[i] = 0
				carry = 1
			elif i == n - 1:
				arr[i] += 1
			elif arr[i] != 9 and carry == 1:
				arr[i] += 1
				carry = 0
			elif arr[i] == 9 and carry == 1:
				arr[i] = 0
				carry = 1
			else:
				continue
		if carry == 1:
			arr.insert(0, 1)
			return arr
		else:
			return arr


class Solution:

	def addOne(self, a, n):
		b = []
		if a[n - 1] == 9:
			for v in a:
				b.append(str(v))
			b = int(''.join(b)) + 1
			return list(str(b))
		else:
			a[n - 1] = a[n - 1] + 1
		return a


class Solution:

	def addOne(self, a, n):
		if a[n - 1] < 9:
			a[n - 1] += 1
			return a
		s = ''
		for x in a:
			s = s + str(x)
		s = int(s)
		s += 1
		b = []
		s = str(s)
		for x in s:
			b.append(int(x))
		return b


class Solution:

	def addOne(self, a, n):
		if a[-1] < 9:
			a[-1] = a[-1] + 1
			return a
		else:
			num = ''
			for i in a:
				num += str(i)
			num = int(num) + 1
			return list(str(num))


class Solution:

	def addOne(self, a, n):
		if a[-1] != 9:
			a[-1] = a[-1] + 1
			return a
		s = ''
		for i in a:
			s = s + str(i)
		s = int(s) + 1
		return str(s)


class Solution:

	def addOne(self, a, n):
		n = len(a)
		if a[n - 1] < 9:
			a[n - 1] += 1
			return a
		else:
			l = list(map(str, a))
			num = int(''.join(l))
			num_1 = str(num + 1)
			res = list(num_1)
			return res


class Solution:

	def addOne(self, a, n):
		flag = 0
		arr = [1]
		for i in range(n - 1, -1, -1):
			if a[i] == 9:
				a[i] = 0
			else:
				a[i] += 1
				flag = 1
				break
		if flag == 1:
			return a
		else:
			for i in range(n):
				arr.append(a[i])
		return arr


class Solution:

	def addOne(self, a, n):
		carry = 1
		for i in range(len(a) - 1, -1, -1):
			x = carry + a[i]
			if x > 9:
				a[i] = x % 10
				carry = x // 10
			else:
				a[i] = x
				carry = 0
		if carry != 0:
			a.insert(0, carry)
		return a


class Solution:

	def addOne(self, a, n):
		i = n - 1
		if a[n - 1] == 9:
			while a[i] == 9:
				a[i] = 0
				i -= 1
				if i < 0:
					a.insert(0, 1)
			if i > 0:
				a[i] += 1
			return a
		else:
			return a[0:n - 1] + [a[n - 1] + 1]


class Solution:

	def addOne(self, a, n):
		a[-1] = a[-1] + 1
		for i in reversed(range(1, len(a))):
			if a[i] != 10:
				break
			a[i] = 0
			a[i - 1] += 1
		if a[0] == 10:
			a[0] = 1
			a.append(0)
		return a


class Solution:

	def addOne(self, a, n):
		c = 1
		for i in range(n - 1, -1, -1):
			a[i] += c
			if a[i] == 10:
				a[i] = 0
				c = 1
			else:
				return a
		if c == 1:
			a.insert(0, 1)
		return a


class Solution:

	def addOne(self, a, n):
		s = ''
		f = 0
		for i in range(len(a) - 1, -1, -1):
			if a[i] == 9:
				a[i] = 0
				f = 1
			else:
				a[i] += 1
				f = 0
			if f == 0:
				break
		if f == 1:
			b = [1]
			for i in a:
				b.append(i)
			return b
		else:
			return a


class Solution:

	def addOne(self, a, n):
		ls = []
		carry = 0
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				x = a[i] + 1
				if x > 9:
					carry = x // 10
					ls.append(x % 10)
				else:
					ls.append(x)
			elif i == 0:
				x = a[i] + carry
				if x > 9:
					ls.append(x % 10)
					ls.append(x // 10)
				else:
					ls.append(x)
			else:
				x = a[i] + carry
				if x > 9:
					carry = x // 10
					ls.append(x % 10)
				else:
					carry = 0
					ls.append(x)
		return ls[::-1]
		return x


class Solution:

	def addOne(self, a, n):
		if a[-1] != 9:
			a[-1] = a[-1] + 1
			return a
		else:
			x = ''
			for i in a:
				x += str(i)
			new = int(x) + 1
			ans = []
			for i in str(new):
				ans.append(i)
			return ans
if __name__ == '__main__':

	def printAns(ans):
		for x in ans:
			print(x, end=' ')
		print()
	tc = int(input())
	while tc:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		printAns(ob.addOne(a, n))
		tc = tc - 1


class Solution:

	def addOne(self, a, n):
		index = len(a) - 1
		while index >= 0 and a[index] == 9:
			a[index] = 0
			index -= 1
		if index < 0:
			a.insert(0, 1)
		else:
			a[index] += 1
		return a
if __name__ == '__main__':

	def printAns(ans):
		for x in ans:
			print(x, end=' ')
		print()
	tc = int(input())
	while tc:
		n = int(input())
		a = list(map(int, input().strip().split()))
		ob = Solution()
		printAns(ob.addOne(a, n))
		tc = tc - 1


class Solution:

	def addOne(self, a, n):
		carry = 1
		for i in range(n - 1, -1, -1):
			a[i] += carry
			carry = a[i] // 10
			a[i] = a[i] % 10
		ans = []
		if carry == 1:
			ans.append(carry)
		for x in a:
			ans.append(x)
		return ans


class Solution:

	def addOne(self, a, n):
		b = []
		for i in range(0, n + 1):
			b.append(0)
		for j in range(n - 1, -1, -1):
			if a[j] != 9:
				a[j] += 1
				break
			else:
				a[j] = 0
		if a[0] == 0:
			b[0] = 1
			return b
		return a


class Solution:

	def addOne(self, a, n):
		add_1 = 0
		carry = 0
		val = 0
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				add_1 = a[n - 1] + 1
				carry = add_1 // 10
				val = add_1 % 10
			else:
				add_1 = a[i] + carry
				carry = add_1 // 10
				val = add_1 % 10
			a[i] = val
		if carry == 1:
			a.insert(0, 1)
		return a


class Solution:

	def addOne(self, arr, n):
		if arr[n - 1] != 9:
			arr[n - 1] += 1
			return arr
		else:
			c = n
			arr[n - 1] += 1
			while c > 1:
				if arr[n - 1] == 10:
					arr[n - 1] = 0
					arr[n - 2] += 1
					n = n - 1
				c = c - 1
			if arr[0] == 10:
				arr[0] = 0
				arr.insert(0, 1)
		return arr


class Solution:

	def addOne(self, a, n):
		n = len(a)
		a[n - 1] += 1
		carry = a[n - 1] / 10
		a[n - 1] = a[n - 1] % 10
		for i in range(n - 2, -1, -1):
			if carry == 1:
				a[i] += 1
				carry = a[i] / 10
				a[i] = a[i] % 10
		if carry == 1:
			a.insert(0, 1)
		return a


class Solution:

	def addOne(self, a, n):
		x = ''
		if a[-1] != 9:
			a[-1] += 1
			return a
		else:
			for i in a:
				x += str(i)
			res = int(x) + 1
			return str(res)


class Solution:

	def addOne(self, a, n):
		s = ''
		for i in a:
			s += str(i)
		x = int(s) + 1
		l = []
		x = str(x)
		for i in x:
			l.append(i)
		return l


class Solution:

	def addOne(self, a, n):
		num = ''
		for i in a:
			num += str(i)
		x = int(num) + 1
		return list(str(x))


class Solution:

	def addOne(self, a, n):
		return str(int(''.join(list(map(str, a)))) + 1)


class Solution:

	def addOne(self, a, n):
		self.a = a
		self.n = n
		sum = 0
		l = []
		if n == 1:
			a[0] += 1
			return a
		for i in range(n - 1, 0, -1):
			if a[i] == 9 and a[i - 1] != 9:
				a[i] = 0
				a[i - 1] += 1
				return a
			elif a[i] == a[i - 1] == 9:
				a[i] = 0
			else:
				a[i] += 1
				return a
		if a[1] == 0 and a[0] != 9:
			a[0] += 1
		elif a[1] == 0 and a[0] == 9:
			a[0] = 0
			a.append(1)
			return reversed(a)
		return a


class Solution:

	def addOne(self, a, n):
		num = int(''.join(map(str, a)))
		plus = num + 1
		res = list(map(int, str(plus)))
		return res


class Solution:

	def addOne(self, a, n):
		s = ''
		b = []
		for i in a:
			s = s + str(i)
		s = str(int(s) + 1)
		for i in s:
			b.append(i)
		return b


class Solution:

	def addOne(self, a, n):
		num = ''.join(map(str, a))
		one = 1
		num = int(num)
		return str(num + one)


class Solution:

	def addOne(self, a, n):
		l = [str(i) for i in a]
		b = str(int(''.join(l)) + 1)
		l = [int(i) for i in b]
		return l


class Solution:

	def addOne(self, a, n):
		a2 = [0] * (n + 1)
		added = False
		for i in range(n - 1, -1, -1):
			if a[i] == 9 and (not added):
				a2[i + 1] = 0
			elif not added:
				a2[i + 1] = a[i] + 1
				added = True
			else:
				a2[i + 1] = a[i]
		if not added:
			a2[0] = 1
		return a2 if a2[0] else a2[1:]


class Solution:

	def addOne(self, a, n):
		b = ''.join(map(str, a))
		c = str(int(b) + 1)
		a = [int(i) for i in c]
		return a


class Solution:

	def addOne(self, arr, n):
		j = n - 1
		carry = 1
		while j >= 0 and carry == 1:
			temp = arr[j] + carry
			if temp == 10:
				arr[j] = 0
				carry = 1
				j -= 1
			else:
				arr[j] = temp
				carry = 0
		if carry == 1:
			return [1] + [0] * n
		return arr


class Solution:

	def addOne(self, a, n):
		for i in range(n):
			a[i] = str(a[i])
		s = ''.join(a)
		s = int(s)
		s = s + 1
		s = str(s)
		a = list(s)
		a = list(map(int, a))
		return a


class Solution:

	def addOne(self, arr, n):
		if arr[n - 1] < 9:
			arr[n - 1] += 1
		else:
			carry = 0
			for i in range(n - 1, -1, -1):
				arr[i] += 1
				carry = arr[i] // 10
				arr[i] = arr[i] % 10
				if carry == 0:
					break
				elif i == 0 and carry > 0:
					arr.insert(0, carry)
		return a


class Solution:

	def addOne(self, a, n):
		x = ''
		for i in range(n):
			x = x + str(a[i])
		x = int(x) + 1
		x = str(x)
		return [k for k in x]


class Solution:

	def addOne(self, a, n):
		s = ''
		for x in a:
			s = s + str(x)
		return str(int(s) + 1)