Plus One

EASY✓ CHIP-TIMEDLC #66 — FULL STATEMENT ↗

The drill: A non-negative integer arrives as an array of its digits, most significant first — add exactly one to the number and hand back the digit array of the result, growing it by a digit only if the addition truly overflows.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A whole, non-negative number arrives split into its individual digits, stored in an array with the most significant digit first — the way the number would be written out by hand.

The task is to add exactly one to that number and hand back the resulting value in the same digit-array form, most significant digit still first, with no extra leading zeros anywhere.

Most additions only touch the last digit, but a trailing run of 9s can carry all the way to the front; if every single digit was a 9, the result grows by one whole new leading digit.

EX 01

digits = [1, 2, 3]

→ [1, 2, 4]

NO CARRY NEEDED

EX 02

digits = [9]

→ [1, 0]

SINGLE DIGIT ROLLS OVER

EX 03

digits = [9, 9, 9]

→ [1, 0, 0, 0]

CARRY RIPPLES THROUGH EVERY DIGIT

digit arrays run up to a few hundred entries long
each entry is a single digit, 0 through 9
the input never carries a leading zero on a multi-digit number
the output may gain one extra leading digit, never more than one

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Rebuilding the whole number, adding one, and re-splitting into digits works — but only because the runtime's integers aren't fixed-width. A real fixed-width integer would overflow long before this array does, so what does the array-only version look like?

HINT 2 THE STRUCTURE

Adding one can only ever ripple through a run of trailing 9s — every digit before that run is completely untouched by the addition.

HINT 3 ONE STEP FROM THE ANSWER

Walk from the last digit backward: if a digit is below 9, increment it and stop immediately — done. If it's a 9, set it to 0 and keep walking left. If the walk falls off the front, every digit was a 9, so prepend a leading 1.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CARRY WALKPATTERN · CARRY FROM THE LAST DIGITdigits = [8, 9, 9, 9]

STEP 1

Digits [8,9,9,9]. Walk from the last digit — a 9 rolls to 0 and carries left, anything below 9 just absorbs the carry and stops.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/plus-one.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        result = digits[:]
        for i in range(len(result) - 1, -1, -1):
            if result[i] < 9:
                result[i] += 1
                return result
            result[i] = 0   # this digit was a 9 — roll to 0 and carry left
        return [1] + result

TIME O(N)SPACE O(1) EXTRAPYTHON · RACE PACE · 9 LN

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        number = int(''.join(str(d) for d in digits)) + 1
        return [int(c) for c in str(number)]

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 4 LN

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] result = new int[n + 1];
        result[0] = 1;
        return result;
    }
}

TIME O(N)SPACE O(1) EXTRAJAVA · RACE PACE · 15 LN

class Solution {
    public int[] plusOne(int[] digits) {
        StringBuilder sb = new StringBuilder();
        for (int d : digits) {
            sb.append(d);
        }
        java.math.BigInteger number = new java.math.BigInteger(sb.toString()).add(java.math.BigInteger.ONE);
        String s = number.toString();
        int[] result = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            result[i] = s.charAt(i) - '0';
        }
        return result;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED