</>Ali · LeetCode
#0066·EasyMath

Plus One

LeetCode #66 · Easy · Math · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Simulate addition with carry

Strategy

  1. 1Start from the last digit and add 1
  2. 2Iterate from right to left, handling carries
  3. 3If a digit becomes 10, set it to 0 and carry 1 to the next position
  4. 4If we reach the beginning and still have a carry, insert 1 at the front
Time
O(n)
n is the number of digits
Space
O(1)
if we don't count the output, O(n) in worst case
Problem description(from LeetCode)

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.

Examples

Example 1
Input:
digits = [1,2,3]
Output:
[1,2,4]
Note:
The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Input: digits = [4,3,2,1] Output: [4,3,2,2] Input: digits = [9] Output: [1,0]

Constraints

  • •1 <= digits.length <= 100
  • •0 <= digits[i] <= 9
  • •digits does not contain any leading 0's.

C++ Solution

solution.cpp
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
    int n = digits.size() - 1;
    digits[n]++;
    while (n >= 0) {
      if (digits[n] == 10) {
        digits[n] = 0;
        if (n > 0) {
          digits[n - 1]++;
        } else {
          digits.insert(digits.begin(), 1);
        }
      }
      n--;
    }

    return digits;
  }
};

More Math problems