66. Plus One

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.

Example:

If the vector has [1, 2, 3], the returned vector should be [1, 2, 4] as 123 + 1 = 124.

Approach:

1. Add 1 to the last digit
2. Forward the carry if exists and continue to the beginning

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<int> plusOne(vector<int>& digits) { int sum, carry = 0, n = digits.size(); //add 1 to the last digit sum = digits[n - 1] + 1; //see if there is a carry generated if(sum > 9){ carry = 1; digits[n - 1] = sum % 10; }else{ //if no carry, add 1 to lsb and return digits[n - 1] = sum; return digits; } //if carry, keep adding till there is no carry for(int i = n - 2; i >= 0; i--){ sum = digits[i] + carry; if(sum > 9){ carry = 1; digits[i] = sum % 10; }else{ //if no carry, return digits[i] = sum; return digits; } } //add 1 to the front if there is carry in the end if(carry){ digits.insert(digits.begin(), 1); } return digits; } };

Here is a link to the ideone solution : http://ideone.com/IbLgNA