Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

[LeetCode Road] Plus One - Solution/C++

Posted on Edited on In Disqus:

66. Plus One

Question:

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Input: digits = [0]
Output: [1]

Constraints:
  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

    • Source code

    Version 1

    Idea:
    At first, add 1 and the last index of element. Check each digits in reverse to get the value of carry. Finally, must be check the final the vale of carry, if carry isn't equal to 0, insert it into begining at vector.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
        vector<int> plusOne(vector<int>& digits) {
            const int len = digits.size();
            int i = len - 1, carry = 0;
            digits[i]++;
            while(i >= 0){
                digits[i] += carry;
                int quotient = digits[i] / 10;
                if(quotient >= 1){
                    digits[i] = digits[i] % 10;
                    carry = quotient;
                }else{
                    carry = 0;
                }
                i--;
            }
            if(carry != 0) digits.insert(digits.begin(), carry);
            return digits;
        }
    };