LeetCode //C - 66. Plus One

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;
}