Problem
Given a non-empty array of digits representing a non-negative integer, increment the integer by one. The most significant digit is at the head.
Example
Input: [1,2,3]
Output: [1,2,4]Input: [9,9]
Output: [1,0,0]Solution
Walk from the rightmost digit. If less than 9, increment and return. If 9, set to 0 and carry. If we exit the loop with carry, prepend 1.
def plus_one(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
return [1] + digitsfunction plusOne(digits) {
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
return [1, ...digits];
}vector<int> plusOne(vector<int>& digits) {
for (int i = digits.size() - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
digits.insert(digits.begin(), 1);
return digits;
}public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
int[] result = new int[digits.length + 1];
result[0] = 1;
return result;
}Complexity
- Time: O(n)
- Space: O(1) usually, O(n) if carry overflows
Explanation
The only case requiring a new array is when all digits are 9 (e.g., [9,9,9] becomes [1,0,0,0]). Otherwise we modify in place.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?