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 Sam K., 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

More Math practice problems

See all Math problems →