Given a non-empty array of digits representing a non-negative integer, increment one to the integer.
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 may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.
Example 2:
Input: digits = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321.
Example 3:
Input: digits = [0] Output: [1]
Constraints:
1 <= digits.length <= 1000 <= digits[i] <= 9
The description was taken from https://leetcode.com/problems/plus-one/.
#O(N) Time, O(1) Spaceclass Solution: def plusOne(self, digits: List[int]) -> List[int]: digits[-1] += 1 for i in range(len(digits) -1, 0 ,-1): if digits[i] != 10: break else: digits[i] = 0 digits[i-1] += 1 if digits[0] == 10: digits[0] = 0 digits.insert(0, 1) return digitsWe can solve this problem by adding one to the last element of the array and if needed, carrying over any ones to previous elements.
Let's start by adding the one to the last element in the array, easy.
digits[-1] += 1
Next, we will then traverse the array backwards and see if we need to carry over any values.
The worst-case scenario would be if we had a chain of nines. We would have to go through the entire chain to carry the one over to its next place.
If we get to a value that isn't ten, we can break because we don't need to carry anything over.
for i in range(len(digits) -1, 0 ,-1): if digits[i] != 10: break
If we are at a ten, we'll need to overwrite the number to zero and carry the one over to the next index.
else: digits[i] = 0 digits[i-1] += 1
If our first element in the array is ten, we'll lastly just need to overwrite the number to zero and prepend the one to the array.
if digits[0] == 10: digits[0] = 0 digits.insert(0, 1)
Once we are done carrying over ones and modifying values in place, we'll return the digits array.
return digits