Math & Bits · 090Easy
Plus One
You are given a large integer as an array of digits, most significant digit first, with no leading zeros. Increment it by one and return the resulting digit array.
Constraints
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
- digits has no leading zeros.
Examples
plusOne([1, 2, 3]) -> [1, 2, 4] plusOne([4, 3, 2, 1]) -> [4, 3, 2, 2] plusOne([9, 9]) -> [1, 0, 0] // the result is LONGER plusOne([0]) -> [1] // the only legal leading zero plusOne([9]) -> [1, 0] // a single 9 grows the array plusOne([1, 9, 9]) -> [2, 0, 0] // the carry stops partway
Edge cases
- All nines grows the array by one digit.
- [0] becomes [1].
- Converting to a Number overflows for 100 digits.
Show the target complexity (spoiler)
- Naive
- Joining to a number, adding 1, and splitting back loses precision beyond 15 digits.
- Target
- O(n) time — walk from the last digit: a digit below 9 increments and returns; a 9 becomes 0 and carries. If the loop ends still carrying, prepend a 1.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/12-math-bits/090-plus-one.js ./practice c 090