66. Plus One

LeetCode

Add and Carry

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int carry = 1;

        for (int i = n - 1; i >= 0; i--) {
            int current = digits[i];
            if (current + carry < 10) {
                digits[i] = current + carry;
                carry = 0;
                break;
            } else {
                digits[i] = current + carry - 10;
            }
        }

        if (carry == 0) {
            return digits;
        } else {
            int[] result = new int[n + 1];
            result[0] = 1;
            return result;
        }

    }
}

Remarks:

  1. TC: $O(n)$, SC: $O(1)$ or $O(n)$ (worst situation).
  2. If there’s an carry in the end, we just return 100000..., because the maximun value that will overflow is 99999....
  3. Could be simplified to:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
         public int[] plusOne(int[] digits) {
             int n = digits.length;
             int carry = 1;

             for (int i = n - 1; i >= 0; i--) {
                 int sum = digits[i] + carry;
                 digits[i] = sum % 10;
                 carry = sum / 10;
                 if (carry == 0) {
                     return digits;
                 }
             }

             // add one digit
             int[] result = new int[n + 1];
             result[0] = 1;
             return result;
         }
     }