Plus One

Easy Subject: Math & Geometry

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

You are given a large integer represented as an integer array digits, where each digits[i] is the ith 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]

Optimal Solution

Python

Approach: Iteration with Carry

Start from the last digit. Add 1. If it becomes 10, set it to 0 and carry over 1 to the next digit. Continue until no carry is left. If the carry propagates past the first digit, insert a 1 at the beginning.

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] == 9:
                digits[i] = 0
            else:
                digits[i] += 1
                return digits

        return [1] + digits