66. Plus One

📝 Problem Details

• Title: 66. Plus One
• Link: https://leetcode.com/problems/plus-one/
• Difficulty: Easy
• Tags/Categories: Math Arrays

given a large integer represented as an array digits ordered from most significant to least significant (left to right) does not contain any leading zeros increment the integer by one and return the resulting array of digits

💭What Were My Initial Thoughts?

- start from the back of the array
- carry a 1 forward to the next element if the current element + 1 is == 10
- if the first element (the largest value) is 9, then we need to emplace a new element of 1 at the front of the array
- return the array

💡 Explanation of Solution

same as initial thoughts

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
      int n = digits.size() - 1;
      
      for (int i = n; i >= 0; --i) { // traverse digits from the last element (least significant)
        // since we begin with the last digit, increasing that digit by one
        // results in overflow.  Therefore, all elements PRIOR to digits[0]
        // need to be considered since there may be additional nines between
        // digits[0], ... , digits[n].
        if (digits[i] == 9) {  
          digits[i] = 0;
        } else {  // current digit is not 9 so we can safely increment by one
          digits[i] += 1;
          return digits;
        }
      }
      // if the program runs to this point, each 9 is now a 0.
      // to get a correct solution, we need to add one more element with 
      // a value of zero AND set digits[0] to 1 (in the most significant position)
      // to account for the carry digit.
      digits.push_back(0);
      digits[0] = 1;
      return digits;
    }
};