Katkat
Back

Add One to Digit Array

IntuitSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle array-based arithmetic and carry-over logic, specifically focusing on edge cases like digit overflow and resizing the array.

Problem Statement

Given a non-empty array of decimal digits representing a non-negative integer, increment the integer by one and return the result as an array of digits.

The digits are stored such that the most significant digit is at the head of the list (index 0). You may assume the integer does not contain any leading zeros, except for the number 0 itself.

Function Signature

def plus_one(digits: List[int]) -> List[int]:

Examples

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

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

Constraints

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

Edge Cases

  • Single digit array [9] should become [1, 0].
  • Arrays with trailing nines [1, 9, 9] should become [2, 0, 0].

Hints

Hint 1

Start by iterating through the array from the last index to the first index.

Hint 2

If the current digit is less than 9, increment it and return the array immediately.

Hint 3

If the current digit is 9, set it to 0 and continue to the next digit to the left; if you finish the loop and still have a carry, prepend a 1 to the array.

Follow-up questions

  • How would you modify your solution if the input was given as a linked list of digits instead of an array?
  • Can you solve this problem if the integer is so large that it is represented as a string?
  • What is the time and space complexity of your current solution in terms of the number of digits `n`?