Katkat
Back

Increment Digit Array

CoinbaseData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

This question tests the ability to handle array-based arithmetic and carry propagation logic, specifically addressing edge cases like array resizing.

Problem Statement

You are given a non-empty array of non-negative integers digits representing a non-negative integer. Each element in the array contains a single digit, and the digits are ordered such that the most significant digit is at the index 0 of the array. The number does not contain any leading zeros, except for the number 0 itself.

Implement a function increment_digit_array(digits: List[int]) -> List[int] that increments the represented integer by one and returns the resulting array of digits.

Constraints

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

Examples

Example 1: Input: digits = [1, 2, 3] Output: [1, 2, 4] Explanation: 123 + 1 = 124.

Example 2: Input: digits = [9, 9] Output: [1, 0, 0] Explanation: 99 + 1 = 100.

Example 3: Input: digits = [0] Output: [1]

Edge Cases

  • Handle sequences of nines (e.g., [9, 9, 9]) which require increasing the array length.
  • Ensure the carry logic stops early if the addition of 1 does not result in a carry-over to the next digit.

Hints

Hint 1

Start by incrementing the last element of the array and check if the result is 10.

Hint 2

If a digit becomes 10, set it to 0 and continue the carry to the digit on its left.

Hint 3

If you iterate through the entire array and still have a carry, prepend a 1 to the front of the array.

Follow-up questions

  • How would you modify your solution if the input represented a number in base-N instead of base-10?
  • What is the time and space complexity of your solution, and can you perform the increment in-place without creating a new list if possible?
  • How would you handle the input if the digits were provided as a linked list instead of an array?