You are given a large integer represented as an integer array digits, where each digits[i] is the ith 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.
Example 1:
Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4].
Example 2:
Input: digits = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321. Incrementing by one gives 4321 + 1 = 4322. Thus, the result should be [4,3,2,2].
Example 3:
Input: digits = [9] Output: [1,0] Explanation: The array represents the integer 9. Incrementing by one gives 9 + 1 = 10. Thus, the result should be [1,0].
Constraints:
1 <= digits.length <= 1000 <= digits[i] <= 9digits does not contain any leading 0's.The Plus One problem represents a non-negative integer as an array of digits. The goal is to add one to the number and return the updated digits while handling any carry that may occur. A common challenge arises when digits like 9 produce a carry that propagates to earlier positions.
The key idea is to traverse the array from right to left. If the current digit is less than 9, you can simply increment it and stop. If the digit is 9, it becomes 0 and the carry moves to the next digit on the left. This process continues until a digit can be incremented without creating another carry.
An important edge case occurs when all digits are 9. In that case, the result requires an additional leading digit (for example, [9,9,9] → [1,0,0,0]). This approach processes each digit at most once, making it efficient for large inputs.
The algorithm runs in O(n) time with minimal additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Right-to-left digit traversal with carry handling | O(n) | O(1) |
NeetCode
This approach involves checking from the last digit to the first and handling the carry manually. Start from the last digit and add one. If it results in 10, set that position to 0 and carry forward the 1 to the next significant digit. If any digit becomes less than 10 after addition, simply return the array as it is. If all digits end with a carry, insert an additional 1 at the beginning.
Time Complexity: O(n), where n is the length of the digits array.
Space Complexity: O(1), as we are modifying the digits array in place.
1def plus_one(digits):
2 for i in range(len(digits) - 1, -1, -1):
3 if digits[iThe Python function iterates over each digit from the back, checking and handling carry-forward. If the digit is less than 9, we increment it and return immediately. If it's 9, we turn it to 0 and continue. If all digits are 9, we handle it by adding a 1 at the front.
This approach involves converting the array of digits into a number, incrementing the number, and then converting it back into an array of digits. This is feasible due to built-in big integer support in several languages.
Time Complexity: O(n) for conversion
Space Complexity: O(n) for storing the string.
1def plus_one(digits):
2 num_str = ''.joinWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The optimal approach is to traverse the digits array from right to left and handle carry propagation. If a digit is less than 9, increment it and return immediately. If it is 9, set it to 0 and continue moving left until the carry stops or a new leading digit is needed.
Yes, Plus One is a common easy-level interview question used by companies including FAANG. It tests understanding of arrays, carry propagation, and handling edge cases such as all digits being 9.
An array or list is the most suitable data structure because the number is already represented as digits. Arrays allow easy access and modification from the end, which is necessary for efficient carry handling.
The least significant digit is at the end of the array, so adding one starts there. If the digit becomes 10, a carry must propagate to the left, which is why the traversal proceeds backward.
The function converts the digits to a string, then a number, increments it, and converts back to the digit list. Python's int handles big integers seamlessly.