Coding problem · Easy · Basics

Plus One

Easy Algorithms & data structures

A non-negative integer is stored as an array of its digits, most significant first (no leading zeros except the number 0 itself). Return the digits of the number plus one.

Example 1

Input: digits = [1,2,3]
Output: [1,2,4]

Example 2

Input: digits = [9,9]
Output: [1,0,0]

Hints

Hint 1

Start from the last digit and add one.

Hint 2

A 9 becomes 0 and carries 1 to the left; if every digit was 9, put a 1 in front.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Walk from the end: if the digit is less than 9, increment it and you're done; otherwise set it to 0 and carry. If the carry passes the first digit, prepend 1.

Reference solution

function plusOne(digits) {
  const out = [...digits];
  for (let i = out.length - 1; i >= 0; i--) {
    if (out[i] < 9) { out[i]++; return out; }
    out[i] = 0;
  }
  return [1, ...out];
}

function plusOne(digits: number[]): number[] {
  const out = [...digits];
  for (let i = out.length - 1; i >= 0; i--) {
    if (out[i] < 9) { out[i]++; return out; }
    out[i] = 0;
  }
  return [1, ...out];
}

def plus_one(digits: list[int]) -> list[int]:
    out = digits[:]
    for i in range(len(out) - 1, -1, -1):
        if out[i] < 9:
            out[i] += 1
            return out
        out[i] = 0
    return [1] + out

<?php

function plusOne(array $digits): array
{
    for ($i = count($digits) - 1; $i >= 0; $i--) {
        if ($digits[$i] < 9) {
            $digits[$i]++;
            return $digits;
        }
        $digits[$i] = 0;
    }
    return array_merge([1], $digits);
}

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

Was this page helpful?