Plus One
EasyPrompt
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] <= 9digitsdoes not contain any leading0's.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach converts the array of digits into a data type that can handle arbitrarily large integers, such as Java's BigInteger. The process involves first building a string from the digit array, parsing it into a BigInteger, performing the addition, and then converting the result back into an array of digits. While straightforward, it's not the most performant solution.
Algorithm
- Create a
StringBuilderto hold the string representation of the integer. - Iterate through the
digitsarray and append each digit to theStringBuilder. - Convert the
StringBuilderto aStringand then construct ajava.math.BigIntegerobject. - Use the
add()method ofBigIntegerto add one to the number. - Convert the resulting
BigIntegerback to aString. - Create a new integer array with a size equal to the length of the result string.
- Iterate through the result string, convert each character back to an integer, and populate the new array.
- Return the new array.
Walkthrough
The core idea is to leverage a high-level library designed for arbitrary-precision arithmetic. Instead of manually handling the carry logic, we delegate the entire addition operation to the BigInteger class.
import java.math.BigInteger; class Solution { public int[] plusOne(int[] digits) { // 1. Convert array to a string representation. StringBuilder sb = new StringBuilder(); for (int digit : digits) { sb.append(digit); } // 2. Create a BigInteger from the string. BigInteger number = new BigInteger(sb.toString()); // 3. Add one. number = number.add(BigInteger.ONE); // 4. Convert the result back to a string. String resultStr = number.toString(); // 5. Convert the string back to an integer array. int[] result = new int[resultStr.length()]; for (int i = 0; i < resultStr.length(); i++) { result[i] = resultStr.charAt(i) - '0'; // Convert char to int } return result; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
The logic is simple to understand and write, as it offloads the complex arithmetic to a built-in library.
It correctly handles all edge cases, including very large numbers and the case where the number of digits increases (e.g., 999 + 1).
Cons
Significantly less efficient due to the overhead of creating multiple objects (
StringBuilder,BigInteger,String) and performing conversions between data types.This approach abstracts away the core arithmetic logic, which might not be what an interviewer is looking for when asking this type of question.
This optimal approach simulates the elementary school method of adding one to a number on paper. We start from the rightmost digit and move left. We add one to the last digit. If it's less than 10, we're done. If it becomes 10, we set it to 0 and carry a 1 to the next digit to the left. This process is repeated until we no longer have a carry or we've processed all digits.
Algorithm
- Get the length of the
digitsarray,n. - Iterate through the array from right to left (from index
n-1down to0). - In each iteration, increment the current digit
digits[i]. - Check if the incremented digit is less than 10. If it is, there is no carry-over. We can immediately return the modified
digitsarray. - If the incremented digit is 10, it means we have a carry. Set the current digit to
0and let the loop continue to the next digit to the left, which will then be incremented in the next iteration. - If the loop completes, it means every digit was a 9, and we have a carry-over from the most significant digit.
- In this special case, create a new array of size
n+1. Set the first element of this new array to1(the carry-over). The remaining elements will default to0. - Return this new array.
Walkthrough
This method directly manipulates the input array to reflect the addition. It's highly efficient because it avoids any data type conversions and only iterates through the array once. Most cases (e.g., [1,2,3]) are resolved very quickly by just modifying the last digit. The only case that requires traversing the whole array is when the digits are all or mostly 9s.
class Solution { public int[] plusOne(int[] digits) { int n = digits.length; // Iterate from the last digit to the first for (int i = n - 1; i >= 0; i--) { // Increment the current digit digits[i]++; // If the digit is now less than 10, there's no carry. // We can return the updated array immediately. if (digits[i] < 10) { return digits; } // Otherwise, the digit was 9, it became 10. Set it to 0 // and the loop will continue to carry over the 1. digits[i] = 0; } // If the loop finishes, it means all digits were 9s. // We need to create a new array with an additional leading 1. // e.g., [9, 9, 9] -> [1, 0, 0, 0] int[] newNumber = new int[n + 1]; newNumber[0] = 1; // The rest of the elements in newNumber are already 0 by default. return newNumber; }}Complexity
Time
O(N)
Space
O(1) for average cases, O(N) for the worst case (input is all 9s)
Trade-offs
Pros
Extremely efficient in both time and space.
Operates in-place for all cases except when the number of digits increases (e.g., 999 + 1).
Avoids overhead from string conversions and
BigIntegerobject creation.
Cons
Requires special handling for the case where all digits are 9, which involves creating a new, larger array.
Solutions
Solution
class Solution {public int[] plusOne(int[] digits) { int n = digits.length; for (int i = n - 1; i >= 0; --i) { ++digits[i]; digits[i] %= 10; if (digits[i] != 0) { return digits; } } digits = new int[n + 1]; digits[0] = 1; return digits; }}/** * @param {number[]} digits * @return {number[]} */ var plusOne = function ( digits,) { for (let i = digits.length - 1; i >= 0; --i) { ++digits[i]; digits[i] %= 10; if (digits[i] != 0) { return digits; } } return [1, ...digits];};class Solution {public: vector<int> plusOne(vector<int> &digits) { for (int i = digits.size() - 1; i >= 0; --i) { ++digits[i]; digits[i] %= 10; if (digits[i] != 0) return digits; } digits.insert(digits.begin(), 1); return digits; }};class Solution: def plusOne(self, digits: List[int]) -> List[int]: n = len(digits) for i in range(n - 1, - 1, - 1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0 return [1] + digits # also ok: return [1] + [0]*n ############ class Solution ( object ): def plusOne ( self , digits ): """ :type digits: List[int] :rtype: List[int] """ carry = 1 for i in reversed ( range ( 0 , len ( digits ))): digit = ( digits [ i ] + carry ) % 10 carry = 1 if digit < digits [ i ] else 0 digits [ i ] = digit if carry == 1 : return [ 1 ] + digits return digitsVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.