Increment an Arbitrary-Precision Integer Or Plus One

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.

[1, 2, 3] => 123

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit. You cannot use built-in functions such as int() and str().

SOLUTION: If you are going to solve this problem 3 edge cases should come into your mind.

Case 1: When there is no 9 digit in the array

Input: [1, 2, 3]

Output: [1, 2, 4]

Case 2: When the last element in the array is 9.

Input: [1, 2, 9]

Output: [1, 3, 0]                       Wrong Output: [1, 2, 10]        

Case 3: When all the elements in the array are 9.

Input: [9, 9, 9]

Output: [1, 0, 0 ,0]                 Wrong Output: [9, 9, 10] ,   [0, 0, 1] 

 

	def plusOne(digits):
	# need to add one at the last
	# python suports -ve index to get last element
	digits[-1] += 1
	# now need to iterate from last element and check whether it is 9 or not
	for i in reversed(range(len(digits))): # to generate index in reverse order
	# now getting last index and check for non 10 numbers
	digits[i] != 10: # [1, 2, 3] case no need to else
	break
	# else it is 10 make it 0 and carry 1
	digits[i] = 0
	digits[i-1] += 1 # adding carry to previous index
	# [1, 2, 9] case handles [1, 3, 0]
	# but this will fail [9, 9 , 9] because python support -ve index
	# this advantage becomes disadvantage in this
	# when it reach at 0 index and make it 0 and add carry to next index
	# however list is exhausted and turned index to -1
	# [0, 0, 1] This will be our output

view raw PlusOne.py hosted with ❤ by GitHub

FINAL SOLUTION:

	def plusOne(digits):
	digits[-1] += 1
	# run loop upto 1 index not at 0 by starting from 1
	for i in reversed(range(1, len(digits))): # to generate index in reverse order
	# now getting last index and check for non 10 numbers
	digits[i] != 10:
	break
	# else it is 10 make it 0 and carry 1
	digits[i] = 0
	digits[i-1] += 1 # adding carry to previous index
	# for end
	# After this check at 0th index if it is 10 or not
	if digits[0] == 10:
	digits[0] == 1 # make it 1 [1, 0, 0]
	digits.append(0) # add zero to last [1, 0, 0, 0] to get 0(1) adding time
	return digits

view raw PlusOne2.py hosted with ❤ by GitHub