Plus One[E,Array,Math]

https://leetcode.com/problems/plus-one/description/

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:

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

Example 2:

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

Example 3:

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.

Easy 난이도라 만만히 보고 들어갔다가 수학때문에 꽤나 고전했다.

생각보다 edge case가 다양했던 문제다.

 

덧셈해서 다음 숫자까지 영향을 받는 경우는 Carry = 1 을 활용허자

 

1. C

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

    for(int i = digitsSize-1;i>=0;i--){
        int sum = carry + digits[i];
        if(sum==10){
            ans[i+1] = 0;
        }else{
            ans[i+1] = sum;
            carry = 0;
        }
    }
    if(carry == 1){
        ans[0] = 1;
        *returnSize = digitsSize+1;
    }else{
        for(int i=0;i<digitsSize;i++){
            ans[i] = ans[i+1];
        }
        *returnSize = digitsSize;}
    return ans;
}

 

2. C++

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int c = 1;
        int size = digits.size();
        for(int i=size-1;i>=0;i--){
            int sum = digits[i] + c;
            if(sum==10){
                digits[i] = 0;
            }else{
                digits[i] = sum;
                c = 0;
            }
        }
        if(c==1) digits.insert(digits.begin(),1);
        return digits;
    }
};

 

3. Python

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

        for i in range(len(digits)-1,-1,-1):
            if digits[i] !=9 :
                digits[i]+=1
                cond = True
                break
            else:
                digits[i]=0

        if not cond:
            digits = [1] + digits
        return digits