Plus One
(#66), Easy
Category: Array, Math
Problem Statement
You are given a large integer represented as an integer array `digits`, where each `digits[i]` is the i-th digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits.
Examples
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: 123 + 1 = 124
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: 4321 + 1 = 4322
Input: digits = [9]
Output: [1,0]
Explanation: 9 + 1 = 10 (new digit added)
Input: digits = [9,9,9]
Output: [1,0,0,0]
Explanation: 999 + 1 = 1000 (carry over all digits)
Approach
Carry-Over Approach (Optimal)
- Start from the last digit (rightmost index of the array).
- Repeat while index ≥ 0:
- - If the current digit is less than 9:
- - Increment the digit by 1.
- - Return the digits array (no further carry needed).
- - Else (digit is 9):
- - Set the digit to 0 (carry 1 to the left).
- If all digits were 9, insert 1 at the beginning of the array.
- Return the updated digits array.
// 🔹 Carry Over Approach
var plusOne = function(digits) {
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
digits.unshift(1);
return digits;
};Explanation / Dry Run:
This approach works without converting the number, and handles all edge cases efficiently. Carry is propagated only when a digit is 9.
Naive Approach (Convert to Number) ❌
- Join the digits into a string and convert it to a number.
- Add one to the number.
- Convert the result back to a string and split into digits.
- Return the resulting array.
// ❌ Naive Approach (Precision issue with large inputs)
var plusOne = function(digits) {
let num = Number(digits.join("")) + 1;
return num.toString().split("").map(Number);
};Explanation / Dry Run:
This method works only for small inputs. JavaScript’s `Number` loses precision beyond 15–16 digits, so it fails for large arrays.
Complexity
Time: O(n) for optimal approach (loop from end to start of digits)
Space: O(1) (in-place modification, ignoring output array)