Plus One

The problem

digits holds the digits of a whole number that is zero or more, in the order you write them: the leftmost digit comes first. There are no extra zeros in front, so only the number 0 starts with a 0. Return the digits of the number that is one larger, written the same way. The answer can be one digit longer than the input.

What to write

function solve(digits: number[]): number[]

Input
digits = [1,2,3]

Output
[1,2,4]

Input
digits = [9]

Output
[1,0]

Constraints

1 ≤ digits.length ≤ 100.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list can hold 100 digits. A JavaScript number is exact only up to 9,007,199,254,740,991, which has 16 digits, so do not count on joining the digits into one number and splitting the result. Adding 1 is a small change: in most numbers nearly every digit comes back as it was.

2. Hint 2: Ask a smaller question

   Add 1 to 1299 on paper. Which digits changed, and which stayed as they were? What made the changes stop where they did?

3. Hint 3: Name the pattern

   On paper you start at the last digit. A 9 turns into 0 and passes a 1 to the digit before it; that 1 is called a carry. The first digit below 9 takes the 1 and the work stops. Working through a number one digit at a time is digit-by-digit arithmetic. The signal: the number arrives as separate digits. Read the lesson on digit-by-digit arithmetic.

4. Hint 4: State the invariant

   While you move from the last digit toward the first, every digit you have passed was a 9 and is now 0, and a single 1 is still waiting to be added. The digits you have not reached yet are unchanged.

5. Hint 5: Sketch the pseudocode

   For each position from the last to the first: if the digit is below 9, add 1 to it and return the list. Otherwise set the digit to 0 and go on. If the loop ends, every digit was a 9: return a new list holding 1 followed by all the zeros.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Propagate a carry backward through trailing nines. If every digit overflows, prepend one.

The slow way

Join the digits into one number, add 1, and split the result back into digits. In Python that works, because its whole numbers have no size limit. A JavaScript number is exact only up to 9,007,199,254,740,991, which has 16 digits. Past that the digits can come back wrong: 9,007,199,254,740,992 plus one returns the same 16 digits.

The insight

Adding 1 only disturbs the end of the number. A last digit below 9 goes up by one and nothing else changes. A 9 turns into 0 and hands the 1 to the digit before it, where the same question is asked again. So the changes stop at the first digit from the right that is not a 9.

Step by step

1. Walk from the last digit toward the first. Adding starts at the ones digit, which is the last item of the list. A 1 that does not fit in its place can only move toward the front.
2. A digit below 9 takes the 1, and the number is finished. A digit from 0 to 8 can grow by one and still be a single digit. Nothing is passed on, so every digit in front of it stays as it was.
3. A 9 becomes 0 and the 1 moves on to the digit before it. 9 plus 1 is 10, which is two digits. The 0 stays in this place and the 1 moves one place to the left. That moving 1 is called a carry.
4. Every digit was a 9: put a 1 in front of the zeros. The carry left the first digit and found no digit to join, so it becomes a new first digit, as when 99 turns into 100. This is the only case where the answer is longer than the input.

The same numbered steps are the comments in each solution.

function solve(digits) {
    // 1. Walk from the last digit toward the first
    for (let i = digits.length - 1; i >= 0; i--) {
        // 2. A digit below 9 takes the 1, and the number is finished
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        // 3. A 9 becomes 0 and the 1 moves on to the digit before it
        digits[i] = 0;
    }
    // 4. Every digit was a 9: put a 1 in front of the zeros
    return [1, ...digits];
}

function solve(digits: number[]): number[] {
  // 1. Walk from the last digit toward the first
  for (let i = digits.length - 1; i >= 0; i--) {
    // 2. A digit below 9 takes the 1, and the number is finished
    if (digits[i] < 9) {
      digits[i]++;
      return digits;
    }
    // 3. A 9 becomes 0 and the 1 moves on to the digit before it
    digits[i] = 0;
  }
  // 4. Every digit was a 9: put a 1 in front of the zeros
  return [1, ...digits];
}

def solve(digits):
    # 1. Walk from the last digit toward the first
    for i in reversed(range(len(digits))):
        # 2. A digit below 9 takes the 1, and the number is finished
        if digits[i] < 9:
            digits[i] += 1
            return digits
        # 3. A 9 becomes 0 and the 1 moves on to the digit before it
        digits[i] = 0
    # 4. Every digit was a 9: put a 1 in front of the zeros
    return [1, *digits]

Example 2, traced

Input
digits = [9]

Output
[1,0]

Why it works

At every moment the digits already passed were all 9s and are now 0s, and one 1 is still waiting to be added in front of them. The first digit below 9 takes that 1, and the list then spells the old number plus one. If no digit is below 9, the number was all 9s, and the next number is a 1 followed by that many zeros.

Time and space

Time O(n), extra space O(1) auxiliary; O(n) returned array. The loop looks at each digit at most once, so the time is O(n) for n digits. The digits are changed inside the given list, and the only extra thing stored is a position: O(1) auxiliary space. The returned list holds up to n + 1 digits: O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Return as soon as a digit below 9 has taken the 1. If the loop goes on, the digits in front go up too and the last line adds a leading 1: [1, 2, 3] becomes [1, 2, 3, 4].
• Handle the number made only of 9s. If the last line returns the list as it is, [9] comes back as [0] instead of [1, 0]: the carry that left the first digit is lost.
• Start at the last digit. Starting at the first one adds the 1 at the wrong end: [1, 2, 3] comes out as [2, 2, 3], which is 100 more, not 1 more.

Pattern

Digit-by-digit arithmetic. Builds on Add Two Numbers.

Keep going