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.
1def plus_one(digits):
2 for i in range(len(digits) - 1, -1, -1):
3 if digits[i] < 9:
4 digits[i] += 1
5 return digits
6 digits[i] = 0
7 return [1] + digitsThe Python function iterates over each digit from the back, checking and handling carry-forward. If the digit is less than 9, we increment it and return immediately. If it's 9, we turn it to 0 and continue. If all digits are 9, we handle it by adding a 1 at the front.
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.