Increment a Digit-Array Integer by One
Company: Intuit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Increment a Digit-Array Integer by One
You are given a non-empty array `digits` in which each element is a single decimal digit (`0`-`9`). The array represents one non-negative integer, written with the **most significant digit at index `0`** and the least significant digit at the last index. The represented integer has no leading zeros, except for the value zero itself, which is represented as the single-element array `[0]`.
Add one to this integer and return the result as a new array of decimal digits, using the same most-significant-first ordering. The carry can propagate through the entire number and may grow the result by one digit.
Because the array can be very long, you must perform the addition digit by digit and handle the carry yourself; do not assume the number fits in a fixed-width built-in integer type.
### Examples
| Input `digits` | Represented integer | Output | Result integer |
|---|---|---|---|
| `[1, 2, 3]` | 123 | `[1, 2, 4]` | 124 |
| `[4, 3, 2, 1]` | 4321 | `[4, 3, 2, 2]` | 4322 |
| `[9]` | 9 | `[1, 0]` | 10 |
| `[9, 9, 9]` | 999 | `[1, 0, 0, 0]` | 1000 |
| `[0]` | 0 | `[1]` | 1 |
### Constraints
- `1 <= digits.length <= 10^4`
- `0 <= digits[i] <= 9`
- `digits` contains no leading zeros, except that the integer `0` is given as `[0]`.
### Output
Return an array of decimal digits (most significant first) representing the incremented integer. The output must itself have no leading zeros.
Quick Answer: This question evaluates a candidate's ability to manipulate arrays and manage carry propagation in a digit-by-digit arithmetic simulation. It is a classic coding interview problem testing edge-case handling, such as trailing nines and array resizing, without relying on built-in big-integer types. The task assesses practical, hands-on array manipulation skill at a foundational algorithmic level.
You are given a non-empty array `digits` in which each element is a single decimal digit (`0`-`9`). The array represents one non-negative integer, written with the most significant digit at index `0` and the least significant digit at the last index. The represented integer has no leading zeros, except for the value zero itself, which is represented as the single-element array `[0]`.
Add one to this integer and return the result as a new array of decimal digits, using the same most-significant-first ordering. The carry can propagate through the entire number and may grow the result by one digit.
Because the array can be very long, you must perform the addition digit by digit and handle the carry yourself; do not assume the number fits in a fixed-width built-in integer type.
Examples:
- `[1, 2, 3]` (123) -> `[1, 2, 4]` (124)
- `[4, 3, 2, 1]` (4321) -> `[4, 3, 2, 2]` (4322)
- `[9]` (9) -> `[1, 0]` (10)
- `[9, 9, 9]` (999) -> `[1, 0, 0, 0]` (1000)
- `[0]` (0) -> `[1]` (1)
The output must itself have no leading zeros.
Constraints
- 1 <= digits.length <= 10^4
- 0 <= digits[i] <= 9
- digits contains no leading zeros, except that the integer 0 is given as [0]
- The returned array must have no leading zeros
Examples
Input: ([1, 2, 3],)
Expected Output: [1, 2, 4]
Explanation: 123 + 1 = 124; only the last digit changes, no carry.
Input: ([4, 3, 2, 1],)
Expected Output: [4, 3, 2, 2]
Explanation: 4321 + 1 = 4322; increment the least significant digit.
Input: ([9],)
Expected Output: [1, 0]
Explanation: 9 + 1 = 10; the carry grows the result by one digit.
Input: ([9, 9, 9],)
Expected Output: [1, 0, 0, 0]
Explanation: 999 + 1 = 1000; carry propagates through every digit and prepends a leading 1.
Input: ([0],)
Expected Output: [1]
Explanation: 0 + 1 = 1; the zero edge case.
Input: ([1, 9, 9],)
Expected Output: [2, 0, 0]
Explanation: 199 + 1 = 200; carry stops at the most significant digit without growing the array.
Input: ([8, 9, 9, 9],)
Expected Output: [9, 0, 0, 0]
Explanation: 8999 + 1 = 9000; carry propagates but the length stays the same.
Hints
- Walk from the least significant digit (last index) toward the front, carrying 1.
- At each position compute (digit + carry): the new digit is the value mod 10 and the new carry is the value divided by 10. You can stop early the moment the carry becomes 0.
- If a carry remains after processing index 0 (the all-9s case, e.g. 999 -> 1000), prepend a 1 to grow the array by one digit.