Plus One
Given a non-empty array of digits representing a non-negative integer, plus 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 contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.
Constraints:
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
- digits does not contain any leading zero
Examples:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123. Incrementing by one gives 124.
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321. Incrementing by one gives 4322.
Input: [9,9,9]
Output: [1,0,0,0]
Explanation: The array represents the integer 999. Incrementing by one gives 1000.
Solutions
Iterative
The solution starts from the end of the array and adds 1 to the current digit. If the sum is greater than or equal to 10, it sets the current digit to the remainder of the sum divided by 10 and carries the quotient to the next iteration. If the carry is greater than 0 after the loop, it adds the carry to the beginning of the array.
def plusOne(digits):
carry = 1; for i in range(len(digits) - 1, -1, -1):
sum = digits[i] + carry; digits[i] = sum % 10; carry = sum // 10; if carry > 0:
digits.insert(0, carry); return digitsFollow-up:
What if the input is a string instead of an array?
