DAY 8
0

# 66. Plus One

## Question

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

### Example1

``````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].
``````

### Example2

``````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].
``````

### Example3

``````Input: digits = [0]
Output: [1]
Explanation: The array represents the integer 0.
Incrementing by one gives 0 + 1 = 1.
Thus, the result should be [1].
``````

### Example4

``````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].
``````

### Constraints

• `1 <= digits.length <= 100`
• `0 <= digits[i] <= 9`
• `digits` does not contain any leading `0`'s.

## 解題

### Think

• 陣列從右到左的順序讀回來，只有在第一個位址(也就是個位數)才加1，加完之後判斷需不需要進位，需要的話`flag_add`設成`True`，在下一個位址的時候就會進位。
• 但是這樣會有一個問題，就是在最高位是`9`的時候(也就是位址為`0`)`(ex: 9 => [9] or 99 => [9, 9])`，如果有進位或加1的情況會有問題，因為沒有下一個位址可以進位了，所以要在額外插入一個`1`

### Code

#### Python

``````class Solution:
def plusOne(self, digits: List[int]) -> List[int]:

for i in range((len(digits)-1), -1, -1):
if i == len(digits)-1:
digits[i] += 1
digits[i] += 1

if (digits[i]-9) > 0:
digits[i] -= digits[i]
if i == 0:
digits.insert(0, 1)
else:

return digits

``````

#### C

``````/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* plusOne(int* digits, int digitsSize, int* returnSize){
int *result = (int*) malloc( sizeof(int) * (digitsSize+1));
bzero(result , sizeof(int)*(digitsSize+1));

int index_digits = 0;

for (int i=digitsSize-1 ; i>=0 ; i--){
if (i == digitsSize-1){
digits[i] += 1;
digits[i] += 1;
}

if ((digits[i]-9) > 0){
digits[i] -= digits[i];
if (i == 0){
for (int j=0 ; j<=digitsSize ; j++){
if (j == 0){
result[j] = 1;
} else {
result[j] = digits[index_digits];
index_digits++;
}
}
*returnSize = digitsSize+1;
return result;
}

}else{
}

}

result = digits;
*returnSize = digitsSize;
return result;
}
``````

### Result

• Python

• C

30天 Leetcode解題之路30