Plus One
Increment the LSB; on 9 set to 0 and carry; if every digit was 9, prepend 1.
2 min read
math array
Problem#
Increment a big integer represented as a digit array (MSB first). Return the new digit array.
Examples#
[1,2,3]→[1,2,4].[9]→[1,0];[9,9]→[1,0,0].
Constraints#
1 <= digits.length <= 100, no leading zeros.
Approach#
Walk from the back. If digit is 9, set to 0 and continue (carry). If digit is < 9, increment and return immediately. If the loop completes without returning, every digit was 9 — prepend 1.
Solution#
class Solution {public: 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; }};func plusOne(digits []int) []int { for i := len(digits) - 1; i >= 0; i-- { if digits[i] < 9 { digits[i]++ return digits } digits[i] = 0 } return append([]int{1}, digits...)}from typing import List
class Solution: def plusOne(self, digits: List[int]) -> List[int]: 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];}class Solution { 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[] out = new int[digits.length + 1]; out[0] = 1; return out; }}function plusOne(digits: number[]): number[] { for (let i = digits.length - 1; i >= 0; i--) { if (digits[i] < 9) { digits[i]++; return digits; } digits[i] = 0; } return [1, ...digits];}Editorial#
Early return on the first non-9 cuts the loop short. Only the all-9s case needs to grow the array — a vector::insert at the front is O(n) but only happens once.
Complexity#
- Time:
O(n). - Space:
O(1)extra (mutates in place).
Concept revision#
Related#