66. 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:
Example 2:
Example 3:
Constraints:
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
- digits does not contain any leading 0’s.
From: LeetCode
Link: 66. Plus One
Solution:
Ideas:
- It iterates from the end of the array, incrementing digits and handling carries.
- If the most significant digit causes a carry, a new array is allocated with an additional digit set to 1 at the beginning.
- The returnSize is used to inform the caller of the new size of the array, which is crucial when a new array is allocated.
Code:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* plusOne(int* digits, int digitsSize, int* returnSize) {
// Initially, set return size equal to the input array size
*returnSize = digitsSize;
for (int i = digitsSize - 1; i >= 0; i--) {
// If the current digit is less than 9, just increment and return
if (digits[i] < 9) {
digits[i]++;
return digits;
}
// Set current digit to 0 if it's 9
digits[i] = 0;
}
// If control reaches here, all digits were 9, so we need a bigger array
int* newArray = (int*)malloc((digitsSize + 1) * sizeof(int));
newArray[0] = 1; // Set the first digit to 1
// Set all other digits to 0
for (int i = 1; i <= digitsSize; i++) {
newArray[i] = 0;
}
// Update the return size to be one more than the input array size
*returnSize = digitsSize + 1;
return newArray;
}