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 C#, similar strategy is employed: iterate, handle carry, and extend the array if all are 0.
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.
1import java.math.BigInteger;
2
3publicJava solution leverages BigInteger for handling large numbers. Convert to a string, parse as BigInteger, increment, then reconstruct the array of digits from the result.