Given a non-negative number represented as a list of digits, add 1 to the number (increment the number represented by the digits). The digits are stored such that the most significant digit is first element of array. 
 
Example 1:
Input: 
N = 3
arr[] = {1, 2, 4}
Output: 
1 2 5
Explanation:
124+1 = 125, and so the Output
Example 2:
Input: 
N = 3
arr[] = {9,9,9}
Output: 
1 0 0 0
Explanation:
999+1 = 1000, and so the output
Your Task:
You don't need to read input or print anything. You only need to complete the function increment() that takes an integer N, and an array arr of size N as input and returns a list of integers denoting the new number which we get after adding one to the number denoted by the array arr.
Expected Time Complexity:  O(N)
Expected Auxilliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
0 <= arr_{i} <= 9

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def increment(self, arr, N):
        # code here 

Solutions:
class Solution:

	def increment(self, arr, N):
		if arr[-1] == 9:
			s = 0
			for i in arr:
				s = s * 10 + i
			return list(str(s + 1))
		else:
			arr[-1] += 1
			return arr


class Solution:

	def increment(self, arr, N):
		a = ''
		if arr[-1] == 9:
			for i in arr:
				a += str(i)
			b = str(int(a) + 1)
			return list(b)
		arr[-1] = arr[-1] + 1
		return arr


class Solution:

	def increment(self, arr, N):
		arr[N - 1] += 1
		carry = 0
		for i in range(N - 1, -1, -1):
			arr[i] += carry
			carry = arr[i] // 10
			arr[i] %= 10
		if carry > 0:
			arr.insert(0, carry)
		return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] < 9:
			arr[-1] += 1
			return arr
		s = ''.join(map(str, arr))
		return list(str(int(s) + 1))


class Solution:

	def increment(self, arr, N):
		res = []
		carry = 1
		i = N - 1
		while i >= 0:
			res.append((carry + arr[i]) % 10)
			carry = (carry + arr[i]) // 10
			i -= 1
		if carry:
			res.append(carry)
		return res[::-1]


class Solution:

	def increment(self, arr, N):
		if arr[-1] < 9:
			arr[-1] = arr[-1] + 1
		elif arr[-1] == 9:
			carry = 1
			for i in range(-1, -N, -1):
				if arr[i] < 9 and carry == 1:
					arr[i] = arr[i] + 1
					carry = 0
				if arr[i] == 9 and carry == 1:
					arr[i] = 0
			if arr[0] == 9 and carry == 1:
				arr[0] = 1
				arr.append(0)
			elif arr[0] < 9 and carry == 1 and (len(arr) > 1):
				arr[0] = arr[0] + 1
		return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] == 9:
			string = ''
			for i in arr:
				string += str(i)
			string = str(int(string) + 1)
			return list(string)
		else:
			arr[-1] += 1
			return arr


class Solution:

	def increment(self, arr, N):
		if arr[N - 1] < 9:
			arr[N - 1] += 1
			return arr
		i = N - 1
		while arr[i] == 9 and i >= 0:
			if i == 0:
				arr[i] = 0
				arr.append(1)
				arr.reverse()
				i -= 1
				break
			else:
				arr[i] = 0
				i -= 1
		if i >= 0:
			arr[i] += 1
		return arr


class Solution:

	def increment(self, arr, N):
		result = []
		inc = 1
		for x in range(N - 1, -1, -1):
			tmp = arr[x] + inc
			result.append(tmp % 10)
			inc = tmp // 10
			if x == 0 and inc > 0:
				result.append(inc)
		return result[::-1]


class Solution:

	def increment(self, arr, N):
		if arr[-1] == 9:
			s = ''
			for i in arr:
				i = str(i)
				s = s + i
			st = int(s) + 1
			st = str(st)
			return st
		else:
			arr[-1] = arr[-1] + 1
			return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] != 9:
			arr[-1] = arr[-1] + 1
			return arr
		c = 1
		for i in range(N - 1, -1, -1):
			arr[i] = arr[i] + c
			c = arr[i] // 10
			arr[i] = arr[i] % 10
		if c != 0:
			arr.reverse()
			arr.append(c)
			arr.reverse()
		return arr


class Solution:

	def increment(self, arr, N):
		c = 1
		k = []
		for i in range(N - 1, -1, -1):
			k.append((c + arr[i]) % 10)
			c = (c + arr[i]) // 10
		if c:
			k.append(c)
		return reversed(k)


class Solution:

	def increment(self, arr, N):
		soDu = 1
		i = N - 1
		while i >= 0 and soDu != 0:
			temp = arr[i] + soDu
			arr[i] = temp % 10
			soDu = temp // 10
			i -= 1
		if soDu == 0:
			return arr
		res = [0] * (N + 1)
		res[0] = soDu
		for i in range(N):
			res[i + 1] = arr[i]
		return res


class Solution:

	def increment(self, arr, N):
		s = ''
		if arr[-1] == 9:
			for i in arr:
				s += str(i)
			ans = int(s) + 1
			s = str(ans)
			for i in range(len(s)):
				if i >= N:
					arr.append(int(s[i]))
				else:
					arr[i] = int(s[i])
			return arr
		else:
			arr[-1] = arr[-1] + 1
			return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] == 9:
			carry = 0
			for i in range(len(arr) - 1, -1, -1):
				if i == N - 1:
					temp = arr[i] + 1
				else:
					temp = arr[i] + carry
				if temp > 9:
					carry = int(str(temp)[0])
					arr[i] = temp % 10
				else:
					arr[i] = temp
					carry = 0
					break
			if carry != 0:
				arr.insert(0, carry)
			return arr
		else:
			arr[-1] = arr[-1] + 1
			return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] != 9:
			arr[-1] += 1
			return arr
		str1 = ''
		for i in arr:
			str1 += str(i)
		res = int(str1) + 1
		return str(res)


class Solution:

	def increment(self, arr, N):
		if arr[N - 1] != 9:
			arr[N - 1] += 1
			return arr
		else:
			r = int(''.join(list(map(str, arr)))) + 1
			l = []
			for i in str(r):
				l.append(int(i))
			return l


class Solution:

	def increment(self, arr, n):
		i = 0
		j = n - 1
		while i < j:
			(arr[i], arr[j]) = (arr[j], arr[i])
			i += 1
			j -= 1
		arr.append(0)
		for i in range(n + 1):
			if arr[i] + 1 <= 9:
				arr[i] = arr[i] + 1
				break
			else:
				arr[i] = 0
		if arr[-1] == 1:
			return arr[::-1]
		return arr[n - 1::-1]


class Solution:

	def increment(self, arr, N):
		if arr[-1] < 9:
			arr[-1] = arr[-1] + 1
			return arr
		s = 0
		for item in arr:
			s = s * 10 + item
		return str(s + 1)


class Solution:

	def increment(self, arr, N):
		rem = 1
		for i in range(1, N + 1):
			if i == N and arr[-i] == 9:
				arr[-i] = 1
				arr.append(0)
				break
			elif arr[-i] == 9 and rem == 1:
				arr[-i] = 0
			else:
				arr[-i] += 1
				rem = 0
				break
		return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] == 9:
			list1 = list()
			wow = ''
			for i in arr:
				wow += str(i)
			wow = int(wow) + 1
			for i in str(wow):
				list1.append(int(i))
			return list1
		else:
			arr[-1] += 1
			return arr


class Solution:

	def increment(self, arr, N):
		if arr[N - 1] <= 8:
			arr[N - 1] = arr[N - 1] + 1
			return arr
		n = int(''.join(map(str, arr)))
		return str(n + 1)


class Solution:

	def increment(self, arr, N):
		c = 1
		for i in range(len(arr) - 1, -1, -1):
			cur = arr[i] + c
			arr[i] = cur % 10
			c = cur // 10
		if c == 1:
			arr.insert(0, 1)
		return arr


class Solution:

	def increment(self, arr, N):
		carry = arr[-1] == 9
		start = N - 1
		if not carry:
			arr[-1] = arr[-1] + 1
			return arr
		while carry and start >= 0:
			temp = arr[start]
			if temp == 9:
				arr[start] = arr[start] + 1 - 10
				start -= 1
			else:
				arr[start] = arr[start] + 1
				carry = False
		if carry:
			arr.insert(0, 1)
		return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] < 9:
			arr[-1] += 1
			return arr
		s = ''
		for item in arr:
			s += str(item)
		return list(str(int(s) + 1))


class Solution:

	def increment(self, arr, n):
		while n >= 1:
			if arr[n - 1] < 9:
				arr[n - 1] = arr[n - 1] + 1
				return arr
			else:
				arr[n - 1] = 0
				n -= 1
		if n == 0:
			ne = []
			ne.append(1)
			ne.extend(arr)
			return ne


class Solution:

	def increment(self, arr, N):
		arr.reverse()
		for i in range(N):
			if arr[i] + 1 < 10:
				arr[i] += 1
				break
			else:
				arr[i] = 0
		if arr[-1] == 0:
			arr.append(1)
		arr.reverse()
		return arr


class Solution:

	def increment(self, arr, N):
		i = N - 1
		while arr[i] == 9:
			arr[i] = 0
			i -= 1
		if i >= 0:
			arr[i] += 1
		else:
			arr = [1] + arr
		return arr


class Solution:

	def increment(self, arr, N):
		i = N - 1
		flag = 0
		while flag == 0:
			arr[i] += 1
			if i > 0 and arr[i] == 10:
				arr[i] = 0
				i = i - 1
			else:
				flag = 1
		nes = ''
		for each in arr:
			nes += str(each)
		ne = list(nes)
		return ne


class Solution:

	def increment(self, arr, n):
		rem = 1
		temp = arr.copy()
		for i in range(n - 1, -1, -1):
			arr[i] = (rem + arr[i]) % 10
			if temp[i] + rem > 9:
				rem = 1
			else:
				rem = 0
		if rem == 1:
			arr.insert(0, 1)
		return arr


class Solution:

	def increment(self, arr, n):
		carry = 1
		for (i, num) in enumerate(reversed(arr)):
			temp = num + carry
			arr[n - 1 - i] = temp % 10
			carry = temp // 10
		if carry != 0:
			arr.insert(0, carry)
		return arr


class Solution:

	def increment(self, arr, n):
		e = n - 1
		add = 1
		while e >= 0 and add != 0:
			ele = arr[e]
			sum = ele + add
			arr[e] = sum % 10
			add = sum // 10
			e -= 1
		if add == 1:
			arr.insert(0, 1)
		return arr


class Solution:

	def increment(self, arr, N):
		carry = 1
		for i in range(N - 1, -1, -1):
			if arr[i] == 9 and carry:
				arr[i] = 0
				carry = 1
			else:
				arr[i] = arr[i] + carry
				carry = 0
		if carry == 1:
			arr.insert(0, 1)
		return arr


class Solution:

	def increment(self, arr, N):
		carry = 1
		for i in range(N - 1, -1, -1):
			new_num = (arr[i] + carry) % 10
			carry = (arr[i] + carry) // 10
			arr[i] = new_num
		if carry:
			arr = [carry] + arr
		return arr


class Solution:

	def increment(self, arr, nums):
		arr.reverse()
		(one, i) = (1, 0)
		while one:
			if i < len(arr):
				if arr[i] == 9:
					arr[i] = 0
				else:
					arr[i] += 1
					one = 0
			else:
				arr.append(1)
				one = 0
			i += 1
		arr.reverse()
		return arr


class Solution:

	def increment(self, digits, N):
		for (i, d) in reversed(list(enumerate(digits))):
			if d < 9:
				digits[i] += 1
				return digits
			digits[i] = 0
		return [1] + digits


class Solution:

	def increment(self, l, N):
		l1 = []
		for i in range(N - 1, -1, -1):
			if l[i] + 1 <= 9:
				l[i] += 1
				break
			else:
				l[i] = 0
				continue
		if l[0] == 0:
			l1.append(1)
			l[:] = l1 + l
		return l


class Solution:

	def increment(self, arr, N):
		carryOver = False
		for i in range(N - 1, -1, -1):
			if carryOver or i == N - 1:
				if arr[i] + 1 == 10:
					arr[i] = 0
					carryOver = True
				else:
					arr[i] += 1
					carryOver = False
		if carryOver:
			arr.insert(0, 1)
		return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] + 1 < 10:
			arr[-1] = arr[-1] + 1
			return arr
		else:
			new_list = []
			carry = 1
			arr[-1] = 0
			i = N - 2
			while i >= 0:
				if arr[i] + 1 == 10:
					arr[i] = 0
					carry = 1
					i -= 1
				else:
					arr[i] = arr[i] + 1
					return arr
			if arr[0] == 0:
				new_list.append(1)
				new_list += arr
				return new_list
			else:
				return arr


class Solution:

	def increment(self, arr, N):
		if N == 1:
			if arr[0] < 9:
				arr[0] += 1
				return arr
			else:
				arr = [1, 0]
				return arr
		else:
			j = 1
			for i in range(N - 1, -1, -1):
				arr[i] += j
				if arr[i] <= 9:
					j = 0
					continue
				else:
					arr[i] = arr[i] % 10
					j = 1
		if j == 1:
			arr.insert(0, 1)
		return arr


class Solution:

	def increment(self, arr, N):
		m = ''
		if arr[-1] < 9:
			arr[-1] += 1
			return arr
		s = ''.join(map(str, arr))
		for i in arr:
			m += str(i)
		return list(str(int(m) + 1))


class Solution:

	def increment(self, arr, N):
		if N == 1 and arr[0] == 9:
			arr[0] = 1
			arr.append(0)
			return arr
		cc = 0
		for u in range(N - 1, -1, -1):
			if u == N - 1:
				if arr[u] + 1 == 10 and u == N - 1:
					arr[u] = 0
					cc = 1
				elif arr[u] + 1 != 10 and u == N - 1:
					arr[u] += 1
			elif arr[u] + cc == 10 and arr[u] != 10:
				arr[u] = 0
				if u == 0:
					arr[u] = 1
					arr.append(0)
			else:
				arr[u] += cc
				cc = 0
		return arr


class Solution:

	def increment(self, arr, N):
		t = 0
		if arr[N - 1] != 9:
			arr[N - 1] += 1
			return arr
		else:
			i = N - 1
			flag = 0
			arr[i] = 0
			i -= 1
			flag = 1
			while i > -1:
				if flag == 1 and arr[i] == 9:
					arr[i] = 0
					flag = 1
				elif flag == 1 and arr[i] != 9:
					arr[i] += 1
					flag = 0
				i -= 1
			if flag == 1:
				arr.insert(0, 1)
			return arr


class Solution:

	def increment(self, arr, N):
		if arr[-1] == 9:
			x = ''
			for i in arr:
				x += str(i)
			x = str(int(x) + 1)
			l = []
			for i in range(len(x)):
				l.append(int(x[i]))
			return l
		else:
			arr[-1] += 1
			return arr


class Solution:

	def increment(self, arr1, N):
		global arr
		arr = arr1
		if arr[-1] < 9:
			arr[-1] = arr[-1] + 1
		else:
			l = list(map(str, arr))
			arr = list(str(int(''.join(l)) + 1))
		return arr


class Solution:

	def increment(self, arr, N):
		for i in reversed(range(len(arr))):
			arr[i] += 1
			if arr[i] < 10:
				return arr
			else:
				arr[i] = 0
		if arr[0] == 0:
			arr.insert(0, 1)
			return arr


class Solution:

	def increment(self, arr, N):
		arr = arr[::-1]
		(one, i) = (1, 0)
		while i >= 0 and i < len(arr):
			if arr[i] + one > 9:
				arr[i] = 0
			elif arr[i] + one < 10:
				arr[i] += one
				one = 0
			i += 1
		if i + 1 > len(arr) and one == 1:
			arr.insert(i, one)
		arr.reverse()
		return arr


class Solution:

	def increment(self, arr, N):
		positon_stopped = len(arr) - 1
		for x in range(len(arr) - 1, -1, -1):
			if arr[x] == 9:
				arr[x] = 0
				positon_stopped = x - 1
			else:
				break
		if positon_stopped < 0:
			arr.insert(0, 1)
		else:
			arr[positon_stopped] += 1
		return arr


class Solution:

	def increment(self, arr, N):
		n = len(arr)
		for i in range(n - 1, -1, -1):
			if arr[i] < 9:
				arr[i] += 1
				return arr
			arr[i] = 0
		arr.insert(0, 1)
		return arr