LeetCode 66 Plus One

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.

Example

Given [1, 2, 3] which represents 123, return [1, 2, 4]. Given [9, 9, 9] which represents 999, return [1, 0, 0, 0].

Difficulty
Easy

Similar Problems

[LeetCode 43] Multiply Strings M

[LeetCode 67] Add Binary E

[LeetCode 369] Plus One Linked List M

Analysis

• Take care of the carry(set the initial value of carry to 1) prepend carry to the begining if needed
• Change the value in-place

1. Cpp solution

use reverse iterator and insert to add value in front of a vector

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) { 
        add(digits, 1);
        return digits;
    }
private:
    // 0 <= digit <= 9 
    void add(vector<int> &digits, int digit) {
        int c = digit; // carry
        for (auto it = digits.rbegin(); it != digits.rend(); ++it) { 
            *it += c;
            c = *it / 10;
            *it %= 10;
        }
        if (c > 0) 
            digits.insert(digits.begin(), 1); 

    }
};

2. Go solution

func plusOne(digits []int) []int {

    n := len(digits)
    carry := 1
    for i := n - 1; i >= 0; i-- {
        tmp := digits[i] + carry
        carry = tmp / 10
        digits[i] = tmp % 10
    }

    if carry > 0 {
        digits = append([]int{carry}, digits...)
        return digits
    }
    return digits
}

Reference