Skip to main content

66. Plus One

easy

Add one to a number represented as a digit array. The textbook carry-propagation problem — and a sneaky test of handling the all-nines case where the array grows.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given a large integer represented as an integer array digits, where each digits[i] is the i-th 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 zero, except the number 0 itself. Increment the large integer by one and return the resulting array of digits.

Constraints

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits does not contain any leading zeros except for the zero itself.

Examples

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]

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Walk from the rightmost digit. If it's less than 9, increment and return.

Hint 2

If it's 9, set it to 0 and carry to the next position.

Hint 3

If the carry propagates past the leftmost digit (e.g., [9,9,9] -> [0,0,0] with leftover carry), prepend a 1.

Hint 4

All-nines and trailing-nines are the two edge cases interviewers test.

Solution approach

Reveal approach

Walk the array from right to left. For each index i: if digits[i] < 9, increment it and return digits (no further carry needed). Else set digits[i] = 0 and continue. If the loop exits without returning (every digit was 9), the array became all zeroes and a new leading 1 is needed: prepend 1 to the array (or allocate a new array of length n + 1 with digits[0] = 1 and the rest 0). Return digits. O(n) time, O(1) extra space in the common case, O(n) only when the array grows. The early return on the first non-9 digit is the optimization that beats the naive 'increment then carry-propagate the whole way'.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • math
  • array

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill Plus One and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →