LeetCode 솔루션

[Easy - wk2 - Q5] 66. Plus One

Chloe 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.08 20:12

6,897 조회
4 댓글
0 추천
0 비추천
목록 게시글 쓰기

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.

익명
작성일 2022.05.11 21:58

def soln(d): # -> [int]
    r = list(reversed(d))
    
    carry = 1
    for i in range(0, len(r)):
        final = r[i] + carry
        r[i] = int(final % 10)
        carry = int(final / 10)
    if carry > 0:
        r.append(carry)
    return list(reversed(r))

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        return soln(digits)

익명
작성일 2022.05.13 00:28

Python

Runtime: 33 ms, faster than 86.26% of Python3 online submissions for Plus One.
Memory Usage: 13.9 MB, less than 60.16% of Python3 online submissions for Plus One.

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry=0
        index=-1
        
        for i in digits[::-1]:
            if carry :
                s=carry + int(i)
            else:
                s=int(i)+1
                
            if s < 10:
                digits[index]=s
                return digits
            else:
                digits[index]=0
                carry=1
            index += -1

        return [1] + digits

Python - Approach 1: Schoolbook Addition with Carry
Time complexity: O(N)
Space complexity: O(N)

Runtime: 66 ms, faster than 8.70% of Python3 online submissions for Plus One.
Memory Usage: 13.8 MB, less than 96.95% of Python3 online submissions for Plus One.

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

        # move along the input array starting from the end
        for i in range(n):
            idx = n - 1 - i
            # set all the nines at the end of array to zeros
            if digits[idx] == 9:
                digits[idx] = 0
            # here we have the rightmost not-nine
            else:
                # increase this rightmost not-nine by 1
                digits[idx] += 1
                # and the job is done
                return digits

        # we're here because all the digits are nines
        return [1] + digits

Runtime: 35 ms, faster than 82.81% of Python3 online submissions for Plus One.
Memory Usage: 13.8 MB, less than 60.16% of Python3 online submissions for Plus One.


class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        strnum = "".join([str(x) for x in digits])
        num = int(strnum)
        resN = num + 1
        return [x for x in str(resN)]

Python

Runtime: 33 ms, faster than 86.26% of Python3 online submissions for Plus One.
Memory Usage: 13.9 MB, less than 60.16% of Python3 online submissions for Plus One.

[code=python]class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry=0
        index=-1
        
        for i in digits[::-1]:
            if carry :
                s=carry + int(i)
            else:
                s=int(i)+1
                
            if s < 10:
                digits[index]=s
                return digits
            else:
                digits[index]=0
                carry=1
            index += -1

return [1] + digits[/code]

Python - Approach 1: Schoolbook Addition with Carry
Time complexity: O(N)
Space complexity: O(N)

Runtime: 66 ms, faster than 8.70% of Python3 online submissions for Plus One.
Memory Usage: 13.8 MB, less than 96.95% of Python3 online submissions for Plus One.

[code=python]class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)

# move along the input array starting from the end
        for i in range(n):
            idx = n - 1 - i
            # set all the nines at the end of array to zeros
            if digits[idx] == 9:
                digits[idx] = 0
            # here we have the rightmost not-nine
            else:
                # increase this rightmost not-nine by 1
                digits[idx] += 1
                # and the job is done
                return digits

# we're here because all the digits are nines
        return [1] + digits[/code]

Runtime: 35 ms, faster than 82.81% of Python3 online submissions for Plus One.
Memory Usage: 13.8 MB, less than 60.16% of Python3 online submissions for Plus One.
[code=python]
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        strnum = "".join([str(x) for x in digits])
        num = int(strnum)
        resN = num + 1
        return [x for x in str(resN)]
[/code]

익명
작성일 2022.05.15 22:07

처음에는 array를 string으로 join 시켜서,

Number() 또는 parseInt() built-in function을 사용하여 숫자화 한 다음,

+=1 플러스 원을 하고,

다시 array로 digit 하나하나를 넣었습니다.

그런데 input으로 받아오는 array에 digit이 16개가 넘어가는 모든 숫자들은 Number() 또는 parseInt() 하는 과정에서
자동으로 0 으로 처리가 되어지더라구요...
이 문제로 지난 주 디스코드 시간에 저희 챗방 운영진분께서 도움을 주셔서, 다른 방법으로 해결 할 수가 있었습니다:)

알고보니 2 byte가 넘어가면, 제한이 걸리다는 내용이었습니다.

const plusOne = (array) => {
  for (let i = array.length-1; i >= 0; i--) {
    if (array[i] === 9) {
      array[i] = 0;
    }
    else  {
      array[i] = array[i]+=1;
      return array;
    }
  }
  array.unshift(1);
  return array;
}

익명
작성일 2022.05.24 10:15

C++
Runtime: 3 ms, faster than 60.70% of C++ online submissions for Plus One.
Memory Usage: 8.9 MB, less than 12.87% of C++ online submissions for Plus One.

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