[LeetCode] 66. Plus One

Problem

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.

Solution

Logic

1. 배열 digits의 마지막 요소에 1을 추가한다.

2. 올림이 발생하면 올림을 메모하고 올림을 이전 요소에 추가해준다.

3. 올림이 발생하지 않으면 계산을 종료한다.

4. 배열 digits의 첫 요소에 올림이 발생하면 길이가 1만큼 더 긴 배열 newDigits을 생성하고 배열 digits의 요소들을 옮겨준 후, 배열 newDigits의 첫 요소에 올림을 반영해준다.

   Code

   class Solution {
    public int[] plusOne(int[] digits) {
        digits[digits.length - 1]++;
        int carry = 0;
        for (int i = digits.length - 1; -1 < i; i--) {
            digits[i] += carry;
            if (digits[i] == 10) { // has carry
                carry = 1;
                digits[i] = 0;
            } else { // has no carry
                carry = 0;
                break;
            }
        } if (digits[0] == 0) { // first element has carry
            int[] newDigits = new int[digits.length + 1];
            for (int i = digits.length - 1; -1 < i; i--)
                newDigits[i + 1] = digits[i];
            newDigits[0] += carry;
            return newDigits;
        } return digits;
    }
   }
   

   Time Complexity

   • 배열 digits의 길이를 n이라 가정했을 때, 아래의 반복문은 최선의 경우 O(1)의 시간 복잡도를 가지고, 최악의 경우 O(n)의 시간 복잡도를 가진다.

     int carry = 0;
     for (int i = digits.length - 1; -1 < i; i--) {
      digits[i] += carry;
      if (digits[i] == 10) { // has carry
        carry = 1;
        digits[i] = 0;
      } else { // has no carry
        carry = 0;
        break;
      }
     }
     

   • 아래 반복문이 실행되면 O(n)의 시간 복잡도를 가진다. 따라서 본 문제는 최선의 경우 O(n), 최악의 경우 O(n)의 시간 복잡도를 가진다.

     if (digits[0] == 0) { // first element has carry
      int[] newDigits = new int[digits.length + 1];
      for (int i = digits.length - 1; -1 < i; i--)
        newDigits[i + 1] = digits[i];
      newDigits[0] += carry;
      return newDigits;
     }