# Given a number represented as an array of digits, plus one to the number

Given a number represented as an array of digits, plus one to the number.

input                    expected

[8,9,9,9]                [9,0,0,0]

[1,0,0,0,0]              [1,0,0,0,1]

[9,8,7,6,5,4,3,2,1,0]    [9,8,7,6,5,4,3,2,1,1]


The following is my C++ code:

vector<int> plusOne(vector<int> &digits)
{
vector<int> result;
vector<int>::iterator it;
int plus = 1;
for (it = digits.end() - 1; it >= digits.begin(); --it)
{
int sum = *it + plus;
if (sum > 9)
{
plus = 1;
result.push_back(0);
}
else
{
result.push_back(sum);
plus = 0;
}
}

if (plus==1)
{
result.push_back(1);
}

reverse(result.begin(), result.end());
return result;
}

• What should [9, 9, 9] do? Should it cause an error, or push anew element onto the vector to return [1, 0, 0, 0]? Mar 12, 2013 at 1:33
• @Dave, it should return [1, 0, 0, 0] Mar 16, 2013 at 18:44

Since you are returning a result.
Pass the parameter by const reference so that you don't accidentally modify it:

vector<int> plusOne(vector<int> const&  digits)


The less than operator is not defined for iterators.
You are just getting lucky.

for (it = digits.end() - 1; it >= digits.begin(); --it)


To iterate over a container in the reverse direction use rbegin() and rend()

for (it = digits.rbegin(); it != digits.rend(); ++it)


To help with efficiency you could reserve space in your result:

result.reserve(digits.size()+1); // The +1 is for cases where the result overflows.
// Note: reserve() does not change the size of the
//       vector just the underlying capacity.


Personally I would have refactored:

    if (sum > 9)
{
plus = 1;
result.push_back(0);
}
else
{
result.push_back(sum);
plus = 0;
}


the body into:

    plus = (sum == 10) ? 1 : 0
sum  = (sum == 10) ? 0 : sum;

result.push_back(sum);

• "The less than operator is not defined for iterators." Not true. std::random_access_iterator supports all equality comparisons. Mar 10, 2013 at 3:00
• @Yuushi: I was very precise in what I said. But lets make the assumption that its std::random_access_iterator. Now its only valid if the iterators are between begin() and end(). In the above code it >= digits.begin() will always be true. At any point where it may potentially be false we have strayed into undefined behavior. Mar 10, 2013 at 3:43
• I don't disagree with you, but I do think the wording could be better. What you've said in your comment should be in your answer. Mar 10, 2013 at 3:52

I can't believe no one is attempting to do this with some sort of carry and modulus operation.

It's not very efficient to branch inside a loop.

// we add 1 by simply initializing the carry to 1 (instead of zero)
int carry = 1;

for (auto it = digits.rbegin(); it != digits.rend(); ++it)
{
int x = *it + carry;
result.push_back(x % 10);
carry = x / 10;
}

if (carry > 0)
{
result.push_back(x % 10);
}

reverse(result.begin(), result.end());


This being an interview question and all I think it's important to point you that you should show that you understand the basics of numeral systems.

The above code contains less corner cases because it's built on top of a rigid formula. This is a more elegant solution and I'd recommend this style of writing simply because it results in less code.

It's unfortunate that the question appears to imply a big endian, in this case it would have been more efficient to store least significant number in the lower range of the vector since that would allow for a faster forward scan (reverse scan is slower) when performing the operation with the carry. Though, it wouldn't surprise me if it was put there just to mess with people's heads.

Sometimes it might be good to come up with a different way of solving a instance problem http://codepad.org/cpJYxKau

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef std::vector<int> IntVector;

int findAddablePosition(const IntVector& src){
int position = src.size() - 1;
while( position >= 0){
if(src[position] < 9) break;
else --position ;
}
return position;
}
IntVector addOne(const IntVector& src){
IntVector result(src);
std::fill( result.begin() + addablePosition + 1, result.end(), 0);
return result;
}

void print(const IntVector& vec){
cout << "[";
for(unsigned i = 0; i < vec.size(); ++i) cout << vec[i] << " ";

cout << "]";
}

int main(){
int input[] = {8,9,9,9};
IntVector vecInput(input,input + sizeof(input)/sizeof(input[0]));
print(vecInput);
cout << " --> ";