Sponsored
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.
1public int[] plusOne(int[] digits) {
2 for (int i = digits.length - 1; i >= 0; i--) {
3 if (digits[i] < 9) {
4 digits[i]++;
5 return digits;
6 }
7 digits[i] = 0;
8 }
9 int[] newDigits = new int[digits.length + 1];
10 newDigits[0] = 1;
11 return newDigits;
12}In Java, we iterate backward over the array. On finding a digit less than 9, we increment and return. If we loop through the entire array, we know the input was all 9s, hence output a new array beginning with 1.
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 = ''.joinThe 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.