Description:
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.
Examples:
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].Solution in Python:
To solve the problem of incrementing a large integer represented as an array of digits, we need to handle the possible carry that might occur when adding one to the last digit. This process involves iterating through the digits array from the end to the beginning, updating the digits and managing the carry appropriately.
Python
class Solution:
def plusOne(self, digits):
"""
Increment the large integer by one and return the resulting array of digits.
:param digits: List[int] - The list of digits representing the large integer.
:return: List[int] - The resulting list of digits after incrementing by one.
"""
n = len(digits) # Length of the digits array
# Traverse the digits array from the end to the beginning
for i in range(n - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1 # Increment the current digit
return digits # Return the result immediately
digits[i] = 0 # Set the current digit to 0 if it was 9
# If all digits were 9, we need to add an additional digit at the front
return [1] + [0] * n
# Example usage:
sol = Solution()
print(sol.plusOne([1, 2, 3])) # Output: [1, 2, 4]
print(sol.plusOne([4, 3, 2, 1])) # Output: [4, 3, 2, 2]
print(sol.plusOne([9])) # Output: [1, 0]Explanation:
- Length Calculation:
- Calculate the length of the digits array using
len(digits).
- Calculate the length of the digits array using
- Traverse from the End:
- Loop through the digits array from the end to the beginning using
range(n - 1, -1, -1). - Check if the current digit is less than 9:
- If true, increment the digit by 1 and return the modified digits array immediately.
- If false (the digit is 9), set the current digit to 0 and continue to the next digit.
- Loop through the digits array from the end to the beginning using
- Handle All 9’s Case:
- If the loop completes without returning (i.e., all digits were 9), prepend a 1 to the array and append
nzeros. This handles the case where the number consists of all 9’s (e.g., 999 + 1 = 1000).
- If the loop completes without returning (i.e., all digits were 9), prepend a 1 to the array and append
This approach efficiently handles the increment operation, taking into account edge cases such as all digits being 9, and ensures that the resulting array of digits is returned correctly.
Solution in Javascript:
JavaScript
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
// Start from the end of the digits array
for (let i = digits.length - 1; i >= 0; i--) {
// If the current digit is less than 9, just increment it by 1
if (digits[i] < 9) {
digits[i]++;
return digits; // Return the array as no further changes are needed
}
// If the current digit is 9, set it to 0
digits[i] = 0;
}
// If all digits were 9, we need to add a leading 1 at the beginning
// Example: [9, 9, 9] becomes [1, 0, 0, 0]
digits.unshift(1);
return digits;
};
// Example usage:
console.log(plusOne([1, 2, 3])); // Output: [1, 2, 4]
console.log(plusOne([4, 3, 2, 1])); // Output: [4, 3, 2, 2]
console.log(plusOne([9])); // Output: [1, 0]Solution in Java:
Java
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length; // Get the length of the digits array
// Traverse the digits array from the end to the beginning
for (int i = n - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++; // Increment the current digit
return digits; // Return the result immediately
}
digits[i] = 0; // Set the current digit to 0 if it was 9
}
// If all digits were 9, we need to add an additional digit at the front
int[] newDigits = new int[n + 1];
newDigits[0] = 1; // Set the first element to 1
// The rest of newDigits are already initialized to 0 by default
return newDigits;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] digits1 = {1, 2, 3};
int[] result1 = sol.plusOne(digits1);
System.out.println(Arrays.toString(result1)); // Output: [1, 2, 4]
int[] digits2 = {4, 3, 2, 1};
int[] result2 = sol.plusOne(digits2);
System.out.println(Arrays.toString(result2)); // Output: [4, 3, 2, 2]
int[] digits3 = {9};
int[] result3 = sol.plusOne(digits3);
System.out.println(Arrays.toString(result3)); // Output: [1, 0]
}
}Solution in C#:
C#
using System;
public class Solution {
public int[] PlusOne(int[] digits) {
int n = digits.Length; // Get the length of the digits array
// Traverse the digits array from the end to the beginning
for (int i = n - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++; // Increment the current digit
return digits; // Return the result immediately
}
digits[i] = 0; // Set the current digit to 0 if it was 9
}
// If all digits were 9, we need to add an additional digit at the front
int[] newDigits = new int[n + 1];
newDigits[0] = 1; // Set the first element to 1
// The rest of newDigits are already initialized to 0 by default
return newDigits;
}
}