Plus One

#296 Most AskedEasy

Plus One #296 Most Asked

Easy

13 views

Topics:

Arrays

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 0's.

Increment the large integer by one and return the resulting array of digits.

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]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `digits` ever be empty or null?
Will the input array `digits` always represent a non-negative integer, or could it contain leading zeros (e.g., `[0, 1, 2]` for 12)?
What is the maximum possible length of the `digits` array? I'm considering potential integer overflow.
Does each element in the array `digits` only contain a single digit (0-9), or could it contain arbitrary integers?
Should I return a new array or modify the input array in place?

Brute Force Solution

Approach

We're given a number represented as a list of digits and need to add one to it. The most straightforward way is to simulate adding one the way we learned in grade school, handling any carry-overs as they arise.

Here's how the algorithm would work step-by-step:

Start from the very last digit in the list.
Add one to that digit.
If the digit becomes ten, set it back to zero and carry-over one to the digit to its left.
Repeat the previous step, moving leftward, until you either don't have a carry-over anymore or you reach the beginning of the list.
If you still have a carry-over after processing the first digit, you need to add a new digit 'one' at the beginning of the list.

Code Implementation

def plus_one_brute_force(digits):
    number_of_digits = len(digits)
    carry = 0
    digits[number_of_digits - 1] += 1

    for i in range(number_of_digits - 1, -1, -1):
        digits[i] += carry
        carry = 0

        # If the digit becomes 10, reset to zero and carry over
        if digits[i] == 10:
            digits[i] = 0
            carry = 1

            # If we're at the beginning and still have a carry, add a new digit
            if i == 0 and carry == 1:
                digits.insert(0, 1)

        else:
            break

    return digits

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of digits (of size n) at most once, starting from the least significant digit. In the worst-case scenario, where all digits are 9, we propagate a carry all the way to the beginning of the list, potentially requiring us to add a new digit. Even in this worst case, we traverse the list a single time. Therefore, the time complexity is directly proportional to the number of digits, n, making it O(n).

Space Complexity

O(1) or O(N) – The algorithm modifies the input list in place, so in most cases, the auxiliary space is O(1) because no additional significant data structures are created. However, if there is a carry-over after processing the most significant digit, a new digit 'one' is added to the beginning of the list. This creates a new list with N+1 elements and would result in O(N) space complexity because a new list may need to be allocated to store all digits, where N is the number of digits in the original list. Because of the potential creation of a new digit, either O(1) or O(N) is valid, but in an in-place implementation and a language that does not automatically resize, the O(1) bound is correct and reflects the plain english approach. The problem description does not preclude this so a true in-place implementation is assumed by the interviewer.

Optimal Solution

Approach

The key is to simulate how you would add one to a number written on paper, starting from the rightmost digit. We need to handle cases where adding one results in a carry-over, which might propagate through the entire number.

Here's how the algorithm would work step-by-step:

Begin by looking at the very last digit.
Add one to that last digit.
If the digit becomes a ten, change it to zero and remember that there's a carry-over of one.
Move to the next digit to the left.
If there was a carry-over, add it to the current digit.
Again, if this digit becomes a ten, change it to zero and remember the carry-over.
Keep repeating steps five and six as you move leftwards through the number.
If you end up with a carry-over even after you've gone through all the digits, it means you need to add an extra digit at the beginning, which should be a one.

Code Implementation

def plus_one(digits):
    number_of_digits = len(digits)
    carry = 1

    for i in range(number_of_digits - 1, -1, -1):
        digit_value = digits[i] + carry

        # If sum is 10, reset digit and carry over
        if digit_value == 10:
            digits[i] = 0
            carry = 1

        # Otherwise, update digit and clear carry
        else:
            digits[i] = digit_value
            carry = 0
            break

    # If there's still a carry after processing all digits
    if carry == 1:
        digits.insert(0, 1)

    return digits

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits array from right to left in a single pass. In the worst-case scenario, where all digits are 9, the carry-over propagates to the most significant digit, requiring modification of all n digits. Even if a new digit is added, it's still a constant time operation after the initial iteration. Therefore, the time complexity is directly proportional to the number of digits, n.

Space Complexity

O(N) – The algorithm iterates through the digits of the input number and potentially creates a new list to store the result, especially if there is a carry-over after processing all the original digits. In the worst-case scenario, where adding one results in a series of carry-overs propagating through all digits (e.g., input [9, 9, 9]), a new list of size N+1 is created, where N is the number of digits in the original input. Therefore, the auxiliary space used is proportional to the number of digits in the input, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an array containing only the digit '1' representing the increment of zero by one or throw an IllegalArgumentException.
Single digit array with value 9	The result should be [1, 0], requiring a new array allocation and carrying over.
Array with all 9s (e.g., [9, 9, 9])	The result should be [1, 0, 0, 0], requiring a new array allocation and handling multiple carries.
Large input array (performance consideration)	The solution should iterate from right to left, avoiding unnecessary operations on earlier digits if no carry is needed.
Array with leading zeros (e.g., [0, 0, 1, 2, 3]) - although technically invalid input according to the problem description	The code should operate correctly on this input, treating it as 123 and producing [1, 2, 4], though input validation could also strip leading zeros initially.
Array contains a non-digit number (e.g. [1, 2, -3])	Throw an IllegalArgumentException since the input must contain only digits.
Array with a digit greater than 9 (e.g. [1, 2, 10])	Throw an IllegalArgumentException since the input digits cannot exceed 9.
Input represents the maximum possible integer value that can be stored	The algorithm inherently handles large numbers represented as arrays of digits, as it avoids direct integer manipulation, thereby dodging overflow issues.

Null or empty input array

How to Handle:

Return an array containing only the digit '1' representing the increment of zero by one or throw an IllegalArgumentException.

Single digit array with value 9

How to Handle:

The result should be [1, 0], requiring a new array allocation and carrying over.

Array with all 9s (e.g., [9, 9, 9])

How to Handle:

The result should be [1, 0, 0, 0], requiring a new array allocation and handling multiple carries.

Large input array (performance consideration)

How to Handle:

The solution should iterate from right to left, avoiding unnecessary operations on earlier digits if no carry is needed.

Array with leading zeros (e.g., [0, 0, 1, 2, 3]) - although technically invalid input according to the problem description

How to Handle:

The code should operate correctly on this input, treating it as 123 and producing [1, 2, 4], though input validation could also strip leading zeros initially.

Array contains a non-digit number (e.g. [1, 2, -3])

How to Handle:

Throw an IllegalArgumentException since the input must contain only digits.

Array with a digit greater than 9 (e.g. [1, 2, 10])

How to Handle:

Throw an IllegalArgumentException since the input digits cannot exceed 9.

Input represents the maximum possible integer value that can be stored

How to Handle:

The algorithm inherently handles large numbers represented as arrays of digits, as it avoids direct integer manipulation, thereby dodging overflow issues.