Leetcode: 66. Plus One

Increment Large Integer by One

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.

Here's a code snippet in C++ that increments the large integer by one and returns the resulting array of digits:

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

Example:

// Input: digits = [1,2,3]
// Output: [1,2,4]
Solution s;
vector<int> digits = {1, 2, 3};
vector<int> result = s.plusOne(digits);
// The large integer represented by the input array is 123.
// Incrementing it by one gives us 124.
// Thus, the output array is [1, 2, 4].
  

Time Complexity:

The time complexity of this solution is O(n), where n is the number of digits in the input array. This is because we iterate over the digits in reverse order, performing constant-time operations for each digit. In the worst case, we may need to insert an additional digit at the beginning of the array, which takes O(n) time in the average case.