Adding strings of integers
I'm trying to write an algorithm for a larger project that will take two strings that are large integers (just using ten-digit numbers for this demo) and add them together to create a final string that exactly represents the sum of the two original strings. I understand that there are potentially more efficient ways to work around this from the start, but I must specifically use strings of large integers as opposed to a long integer.
My thinking was to take the two original lines, reverse them so that their position, tenth position, etc. all lined up correctly to add. Then, one position at a time, convert the characters from strings to single integers and add them together, and then use that sum as one position or otherwise for the final string, which, once completed, will also be reversed back to the correct character order.
Where I ran into difficulties, I think that when preparing for an event in which two integers from the corresponding positions in their rows are added to a sum greater than 9, and then I will carry over some remainder to the next position. For example, if I had 7 and 5 in my positions that would add to 12, I would keep 2 and add 1 to the tens position after it looped back for the tens operation.
I am not getting results that are in no way accurate and after a lot of time bumping into myself trying to fix my algorithm, I'm not sure what I need to do to fix it.
Hopefully my intended process is clear and someone can point me in the right direction or fix a bug I may have in my program.
Thanks in advance.
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
int main()
{
string str1 = "1234567890", str2 = "2345678901"; //Two original strings of large integers
string rev_str1, rev_str2;
int int1 = 0, int2 = 0;
string final; //Final product string, sum of two original strings
int temp_int = 0, buffer_int, remainder = 0;
string temp_str = "", buffer_str;
char buffer[100] = {0};
cout << "str1 = " << str1 << endl;
cout << endl;
cout << "str2 = " << str2 << endl;
cout << endl;
rev_str1 = string(str1.rbegin(), str1.rend());
rev_str2 = string(str2.rbegin(), str2.rend());
for (int i = 0; i < 10; i++)
{
buffer_str = rev_str1.at(i);
int1 = atoi(buffer_str.c_str());
buffer_str = rev_str2.at(i);
int2 = atoi(buffer_str.c_str());
buffer_int += (int1 + int2 + remainder);
remainder = 0;
while (buffer_int > 9)
{
buffer_int -= 10;
remainder += 10;
}
temp_str = itoa(buffer_int, buffer, 10);
final += temp_str;
}
final = string(final.rbegin(), final.rend());
cout << "final = " << final << endl;
cout << endl;
}
source to share
Here's what I came up with. It's just for two terms; if you have more, you will have to adjust things a little, in particular, to wrap, which can be more than 19, and the way the resulting string is distributed:
#include <iostream>
#include <string>
using namespace std;
int main()
{
// Two original strings of large integers
string str1 = "1234567890",
str2 = "2345678901234";
// Zero-padd str1 and str2 to the same length
size_t n = max(str1.size(), str2.size());
if (n > str1.size())
str1 = string(n-str1.size(), '0') + str1;
if (n > str2.size())
str2 = string(n-str2.size(), '0') + str2;
// Final product string, sum of two original strings.
// The sum of two integers has at most one digit more, for more inputs make
// below reverse_iterator a back_insert_iterator, then reverse the result
// and skip the removal of the padding.
string final(n+1, '0');
// The carry
char carry = 0;
// Iterators
string::const_reverse_iterator s1 = str1.rbegin(), e = str1.rend(),
s2 = str2.rbegin();
string::reverse_iterator f = final.rbegin();
// Conversion
for (; s1 != e; ++s1, ++s2, ++f)
{
// Bracketing to avoid overflow
char tmp = (*s1-'0')+(*s2-'0') + carry;
if (tmp > 9)
{
carry = 1;
tmp -= 10;
}
else
{
carry = 0;
}
*f = tmp + '0';
}
final[0] = carry + '0';
// Remove leading zeros from result
n = final.find_first_not_of("0");
if (n != string::npos)
{
final = final.substr(n);
}
cout << "str1 = " << str1 << endl
<< "str2 = " << str2 << endl
<< "final = " << final << endl;
}
source to share
Your problem is that you are carrying 10 seconds instead of 1s. When you add 19 + 5
, you get 4 positions in position and add an extra 1 in position 10 seconds. You wouldn't add 10 additional 10 positions.
You just need to change this line: remainder += 10;
to remainder += 1;
.
Also, this loop while
is unnecessary if you have more than two additions. However, when you only add two digits at a time, the biggest add-on you can have 9 + 9
, which only contains 1.
source to share