Problem
Given an array of digits digits representing a non-negative integer, increment the integer by one and return the resulting array of digits.The digits are arranged so that the most significant digit is at the beginning of the array, and each element contains a single digit.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
digits = [1, 2, 3]Output
[1, 2, 4]Input
digits = [9, 9, 9]Output
[1, 0, 0, 0]Solution
This solution uses Array Traversal and Carry Propagation. We start from the last digit because adding one affects the number from right to left.If the current digit is less than 9, we simply increment it by one and return the array because there is no carry to propagate further.
If the current digit is 9, adding one changes it to 0 and the carry continues to the next digit on the left.
If every digit is 9, all digits become 0. In this case, the result requires one additional digit at the beginning, so we create an array containing 1 followed by zeroes.
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[] result = new int[digits.length + 1];
result[0] = 1;
return result;
}
}Complexity
In the worst case, when all digits are 9, the entire array is traversed once. Therefore, the time complexity isO(n), where n is the number of digits.
For most inputs, the operation is performed directly on the input array. In the special case where all digits are 9, a new array of size
n + 1 is required. Therefore, the extra space complexity is O(n) in the worst case.