5
\$\begingroup\$

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;  
}
\$\endgroup\$
  • \$\begingroup\$ What should [9, 9, 9] do? Should it cause an error, or push anew element onto the vector to return [1, 0, 0, 0]? \$\endgroup\$ – David Mar 12 '13 at 1:33
  • \$\begingroup\$ @Dave, it should return [1, 0, 0, 0] \$\endgroup\$ – Fihop Mar 16 '13 at 18:44
  • \$\begingroup\$ Was C++ a requirement? \$\endgroup\$ – mheinzerling May 14 '13 at 8:41
4
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ "The less than operator is not defined for iterators." Not true. std::random_access_iterator supports all equality comparisons. \$\endgroup\$ – Yuushi Mar 10 '13 at 3:00
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin York Mar 10 '13 at 3:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Yuushi Mar 10 '13 at 3:52
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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){
  int addablePosition= findAddablePosition(src);
  IntVector result(src);
  result[addablePosition] += 1;
  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 << " --> ";
   print( addOne(vecInput) );
 return 0;
}
\$\endgroup\$
  • \$\begingroup\$ does the code work for [9,9,9]? \$\endgroup\$ – Fihop Mar 16 '13 at 20:01
  • \$\begingroup\$ no not for that case just need to check if addablePosition is -1, if so then push front and zero-fill the tail. \$\endgroup\$ – dchhetri Mar 17 '13 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.