Plus One
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 <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.
My Solution
We can solve this using a Java ArrayList to keep track of the incremented digits and a carry. We initialize carry to 1 because we are incrementing by 1. Then the new digit would just be (digit + carry) % 10 and the new carry would be (digit + carry) / 10. We then have to remember to add an extra digit for the carry at the end if the carry ends up being 1. Finally we just add all the digits to the output array in reverse order.
Time complexity would be O(n). Space Complexity would also be O(n).
class Solution {
public int[] plusOne(int[] digits) {
List<Integer> out = new ArrayList<>();
int carry = 1;
int n = digits.length;
for (int i = n-1; i >= 0; i--) {
int num = digits[i] + carry;
out.add(num % 10);
carry = num / 10;
}
if (carry > 0) {
out.add(carry);
}
n = out.size();
int[] arr = new int[n];
for (int i = n-1; i >= 0; i--) {
arr[i] = out.get(n-1-i);
}
return arr;
}
}