We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Plus One

Number: 66

Difficulty: Easy

Paid? No

Companies: Google, Meta, Amazon, Intuit, Microsoft, Bloomberg, TikTok, Visa, Adobe, Uber, Apple, Yahoo, Agoda, tcs

Problem Description

Given an array of digits representing a large integer (with the most significant digit at index 0), increment the number by one and return the resulting array of digits without any leading zeros.

Key Insights

  • The digits are stored from most significant to least significant.
  • Start processing from the least significant digit (end of array) to handle potential carry.
  • Carefully handle the case where all digits are 9, in which case an additional digit is needed.
  • Use an in-place update approach to reduce extra space usage when possible.

Space and Time Complexity

Time Complexity: O(n) in the worst-case, where n is the number of digits. Space Complexity: O(n) in the worst-case for the output array (when an extra digit is added).

Solution

We iterate from the end of the digits array towards the beginning, adding one to the current digit. If the digit becomes 10, we set it to 0 and propagate the carry to the next digit. If no carry is needed, we can return the result immediately. If we finish processing the array and still have a carry (e.g., the number was all 9s), we create a new array with one extra digit at the beginning set to 1.

Code Solutions

# Function to add one to the array of digits
def plusOne(digits):
    # Process digits starting from the least significant digit
    for i in range(len(digits) - 1, -1, -1):
        # Add one to the current digit
        digits[i] += 1
        # Check if digit is less than 10, no carry needed
        if digits[i] < 10:
            return digits  # No further carry, return the result
        # Set current digit to 0 because of carry over
        digits[i] = 0
    # If carry remains after processing all digits, add a new digit at start
    return [1] + digits

# Example usage
# print(plusOne([1, 2, 3]))  # Output: [1, 2, 4]
← Back to All Questions