Katkat
Back

Increment a Digit-Array Integer by One

IntuitSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform manual addition on an array representing a large integer, specifically handling carry propagation and dynamic resizing when the integer overflows its current digit count.

Problem Statement

You are given a non-empty array of digits digits representing a non-negative integer. Each element in the array represents a single digit of the integer, ordered from most significant to least significant (e.g., [1, 2, 3] represents 123).

Your task is to increment the integer by one and return the resulting array of digits.

Constraints

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

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.

Function Signature

def plusOne(digits: list[int]) -> list[int]:

Hints

Hint 1

Start from the last element of the array and work your way backwards.

Hint 2

If a digit is less than 9, you can simply increment it and return the array since no further carry will propagate.

Hint 3

If a digit is 9, it becomes 0, and you must carry the 1 to the next position to the left; if you exhaust all digits and a carry remains, prepend a 1 to the result.

Follow-up questions

  • How would your approach change if the input was given as a linked list instead of an array?
  • What is the time and space complexity of your solution, and can it be optimized?
  • How would you modify the function to support adding an arbitrary integer `k` rather than just 1?