LeetCode 66 Solution (Easy)

Difficulty: Easy

Categories: Math, Arrays

Language(s): C++

Complexity: O(N) time , O(1) space

---

Solution Video

Coming Soon! :)

---

Problem Summary

This problem deals with Carry Propagation.

We are given a non-negative number represented as an array of digits in most significant to least significant order. For instance, if our input was meant to represent 101, we would recieve the following:

[1,0,1]

Our job is to manipulate and return the input array representing the value that results from adding 1 to the original represented number. So for our previous example , 101 + 1 would equal 102, so we would return :

[1,0,2]

---

Edge Cases, Hints, and Things to Consider

• How do you handle when an addition event creates a value greater than 9 in a given index?
• What happens when the most significant digit (index 0) carries after propogation?
• How do we know when to stop, when is the array ready?

---

Intuition / High-Level Approach

Since the array is meant to represent a base-10 integer, we know:

1. Each index can only hold a digit 0–9.
2. When a digit becomes greater than 9 after addition, we:
   • keep the ones place in the current index, and
   • carry the tens place into the next, more significant position.

Knowing this, our approach should be to:

1. Start from the least significant digit (the last index).
2. Add 1 to that digit.
3. If it becomes less than 10, we’re done — just return the array.
4. If it becomes 10 or greater, set it to it's value mod 10, and propagate a carry of 1 to the next, more significant digit.
5. Repeat this process moving left until there is no more carry.

Solution

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        const int N = digits.size();
        int carry = 1;  
        for(int i = digits.size()-1 ; i >= 0 ; i--){
            digits[i] += carry;
            if(digits[i] > 9){
            carry = digits[i]/10;
            digits[i] %= 10;
            }
            else return digits;
        }
        if(carry > 0){
            digits.insert(digits.begin(), carry);
        }
        return digits; 
    }
};