Description#
Given a non-empty array of digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The input array represents the integer 123.
Example 2:
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The input array represents the integer 4321.
Approach#
- Different array operations are mainly divided into cases where the last digit is 9 and cases where it is not 9. If the last digit is not 9, simply add one to the last digit and return the array.
- If the last digit is 9, it can be further divided into cases where all digits are 9 and cases where not all digits are 9. If all digits are 9, the size of the array needs to be increased, with the first digit being 1 and all other digits being 0.
- If not all digits are 9, traverse the array from the back. If a digit is 9, set it to 0. If a digit is not 9, add one to it and return the array.
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* plusOne(int* digits, int digitsSize, int* returnSize){
int* result;
// If the last digit is not 9
if(digits[digitsSize - 1] != 9) {
result = (int*)malloc(sizeof(int)*digitsSize);
memcpy((void*)result,(void*)digits,sizeof(int)*digitsSize);
*returnSize = digitsSize;
result[digitsSize - 1] = digits[digitsSize - 1] + 1;
return result;
}
/* If the last digit is 9 */
for(int i=digitsSize - 1;;i--) {
if(digits[i] != 9)
break;
if(i == 0) {
// If all digits are 9
*returnSize = digitsSize + 1;
result = (int*)malloc(sizeof(int)*(*returnSize));
result[0] = 1;
for(int j=1;j<*returnSize;j++)
result[j] = 0;
return result;
}
}
// If not all digits are 9
*returnSize = digitsSize;
result = (int*)malloc(sizeof(int)*(digitsSize));
int not_9_num = digitsSize - 1;
for(;not_9_num >= 0;not_9_num--) {
if(digits[not_9_num] != 9)
break;
result[not_9_num] = 0;
}
memcpy(result,digits,sizeof(int) * (not_9_num + 1));
result[not_9_num] = digits[not_9_num] + 1;
return result;
}