I'm going to ignore that using a string is inefficient for this type of thing (each char could represent 256 values, theoretically, but you only represent 10).
std::string AddStringNumbers(std::string n1, std::string n2) {
This is a big red flag for me. You are using std::string to represent your numbers; use a class instead. Defining a class is quick and easy:
class BigNumber {
std::string value_;
public:
explicit BigNumber(std::string value)
: value_{ std::move(value) }
{}
std::string const& value() const { return value_; }
};
BigNumber operator+(BigNumber const& lhs, BigNumber const& rhs);
You could even define the operator+ function inline. To put it simply, "stringly typed" values should be avoided.
std::string AddStringNumbers(std::string n1, std::string n2) {
You also take n1 and n2 by value. This means that the strings have to be copied in (sometimes they can be moved, but for many cases, copied). All that copying is wasteful when you really don't need a copy. Take them by const& instead to save the copies.
Small things to note:
sums.insert(sums.begin(), 0). Inserting something into the beginning of a string or a vector is inefficient. This is because every element has to be copied and shifted over one to the right. Try to avoid this if at all possible.n1.length(). I recommend using n1.size() as it's more consistent with other standard library containers, but that comes down to personal preference.
Your algorithm:
- Make the strings the same length (e.g.
"0000193" and "1234567")
- Compute the sums for each digit (
1, 2, 3, 4, 6, 15, 10)
- Transfer carries (from the right) (
1, 2, 3, 4, 7, 6, 0)
- Convert back into a string
This algorithm is wasteful. The algorithm for addition that we learn in primary school is usually something more like:
- Right align the numbers
- From the right:
- Add the two digits, plus the carry if there is one.
- Write the ones digit below in the result.
- Write the tends digit above in the carry
This immediately gives two observations:
- You don't need to pad the strings; if we could just iterate from the right side of the strings, it would work.
- You don't need to compute sums for each digit before constructing the entire string; we can compute and construct as we go.
Point 1:
Luckily for us, std::string has something that allows us to iterate in reverse: rbegin(). string.rbegin() returns an iterator. So we can write this:
auto n1Iter = n1.rbegin();
auto n2Iter = n2.rbegin();
auto n1End = n1.rend();
auto n2End = n2.rend();
Note that auto means that we don't have to write out the type, which would be something like std::string::reverse_iterator (or since we take the string as const&, std::string::const_reverse_iterator). I strongly recommend using auto in almost all places.
Also note that if you stored your numbers backward, the work would be slightly easier.
Point 2:
We can estimate the resulting size we need as max(n1.size(), n2.size()) + 1. This might be 1 more digit than we need, though.
std::string result;
result.resize(std::max(n1.size(), n2.size()) + 1);
auto resultIter = result.rbegin(); // This iterator is modifiable; we can store results into it
We need to keep track of the carry:
int carry = 0; // You might want to use std::uint8_t or other types, but int will work
Now we can iterate over the two strings:
// We have to consider that either number could be smaller.
// You could also ensure that n1Iter/End always refer to the shorter
// or longer string, which might simplify the following logic a bit
while (n1Iter != n1End && n2Iter != n2End) {
int digitSum = (*n1Iter - '0') + (*n2Iter - '0') + carry;
carry = digitSum / 10;
int digit = digitSum % 10;
*resultIter = static_cast<char>(digit + '0');
++resultIter;
++n1Iter;
++n2Iter;
}
Note that instead of (char)(digit + '0'), I used static_cast<char>(...). It is recommended in C++ that you use the appropriate cast.
auto remainingIter = (n1Iter == n1End) ? n2Iter : n1Iter;
auto remainingEnd = (n1Iter == n1End) ? n2End : n1End;
while (remainingIter != remainingEnd) {
int digitSum = (*remainingIter - '0') + carry;
carry = digitSum / 10;
int digit = digitSum % 10;
*resultIter = static_cast<char>(digit + '0');
++resultIter;
++remainingIter;
}
At this point, the string will contain the sum, plus possibly an irrelevant char at the beginning, which we have to detect and remove if necessary:
return result[0] == '\0' ? result.substr(1) : result;
Putting it all together:
class BigNumber {
std::string value_;
public:
explicit BigNumber(std::string value)
: value_{ std::move(value) }
{}
std::string const& value() const { return value_; }
};
BigNumber operator+(BigNumber const& lhs, BigNumber const& rhs) {
auto const& n1 = lhs.value();
auto const& n2 = rhs.value();
auto n1Iter = n1.rbegin();
auto n2Iter = n2.rbegin();
auto n1End = n1.rend();
auto n2End = n2.rend();
std::string result;
result.resize(std::max(n1.size(), n2.size()) + 1);
auto resultIter = result.rbegin();
int carry = 0;
while (n1Iter != n1End && n2Iter != n2End) {
int digitSum = (*n1Iter - '0') + (*n2Iter - '0') + carry;
carry = digitSum / 10;
int digit = digitSum % 10;
*resultIter = static_cast<char>(digit + '0');
++resultIter;
++n1Iter;
++n2Iter;
}
auto remainingIter = (n1Iter == n1End) ? n2Iter : n1Iter;
auto remainingEnd = (n1Iter == n1End) ? n2End : n1End;
while (remainingIter != remainingEnd) {
int digitSum = (*remainingIter - '0') + carry;
carry = digitSum / 10;
int digit = digitSum % 10;
*resultIter = static_cast<char>(digit + '0');
++resultIter;
++remainingIter;
}
return BigNumber{
result[0] == '\0' ? result.substr(1) : result
};
}
