66. Plus One

Description

The plusOne function takes a vector of integers representing a non-negative integer with each digit stored in a separate element. The function increments this integer by one and returns the resulting vector of digits.

Intuition

To increment the integer represented by the vector, we start from the least significant digit (rightmost) and add one. If the addition causes a digit to roll over from 9 to 0, we propagate this carry to the next more significant digit.

Approach

1. Traversal from End: Start iterating from the last digit of the vector.
2. Digit Handling: - If the digit is less than 9, simply increment it and return the updated vector. - If the digit is 9, set it to 0 and move to the next more significant digit.
3. Overflow Handling: - If all digits are processed and all were 9s, insert a new digit (1) at the beginning of the vector to handle the carry-over.

Complexity

Time Complexity:

O(n), where n is the number of digits in the vector. Each digit is processed at most once.

Space Complexity:

O(1) if we disregard the space used to return the new vector. The modification is done in-place.

Code

C++

class Solution {
public:
    std::vector plusOne(std::vector& digits) {
        int n = digits.size();
        // Start from the last digit
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

Python

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):

            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0
        return [1] + [0] * n

Java

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] result = new int[n + 1];
        result[0] = 1;  // The new most significant digit
        return result;
    }
}

JavaScript

var plusOne = function (digits) {
        let res = BigInt(digits.join(""))
        let inc = String(BigInt(res)+1n)
        //console.log(inc)
         let t = inc.toString().split("").map(Number)
        
        return t

};