0066-plus-one.c

/*
    Given an integer array where the elements represent the digits of a number,
    return the resulting array when we add one to it.
    Ex. digits = [1,2,3] + 1 -> [1,2,4]

    The length of the array after adding 1 will either remain the same or 
    increase by 1. So we keep the size of the result array as n+1 during the 
    start. We iterate from the last digit to the first digit backwards and 
    keep track of the carry generated by the previous digit. 
    
    If there is a carry left at the end, the addition caused the length to 
    increase, so we return the result. Else if there is no carry, the length 
    remained constant, so we skip the first element of result and return.

    Time: O(n)  
    Space: O(n)
*/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize){
    
    // Reserve the result with a digitsSize+1 size array
    int* result = (int*) malloc(sizeof(int)*(digitsSize+1));
    *returnSize = digitsSize+1;
    result[0] = 1;
    
    int carry = 1;
    for (int i = digitsSize; i > 0; --i) {
        int sum = digits[i-1] + carry;
        carry = sum/10;
        sum = sum%10;

        result[i] = sum;
    }
    
    if (carry)
        return result;
    
    // Skip the additional element which was reserved for carry
    *returnSize = digitsSize;
    return result+1;
}