Most of the popular programming languages like C/C++, Java, C# provide primitive data types (int, long) to hold values up to only a specific range.
A 64-bit integer can store only store numbers in the range of -264 to 263-1. This can store numbers containing roughly 19-20 digits.
What if we have to deal with even bigger numbers.
For example, numbers such as 1298372305835723862093487348
We have to implement our own methods to do arithmetic on such numbers. Just like the following we do for addition.
7 8 2 9 3 4 3
3 4 5 6 9 8 1
1 7 6 5 2 3 5
2 1 2 1 1 0 —->carry
—————-
1 3 0 5 1 5 5 9
In this post we will see how can we implement addition of a list of big numbers. C++ does not have a standard library data structure/algorithms to do so. How ever Java provides a BigInteger class for this purpose.
We assume that these big numbers are represented as strings.
Here is how it is implemented in C++.
Here is how it is implemented in Java. See how BigInteger made our life easier!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <string> | |
| #include <sstream> | |
| #include <vector> | |
| using namespace std; | |
| //This function assumes that all the numbers have equal number of digits | |
| string getSum( vector<string>& numbers) | |
| { | |
| stringstream ss; | |
| int i,j; | |
| int d, carry = 0; | |
| for( i = numbers[0].size()-1; i >= 0; i-- ) | |
| { | |
| d = carry; | |
| for( j = 0; j < numbers.size(); j++ ) | |
| { | |
| d += numbers[j][i] - '0'; | |
| } | |
| ss << d%10; | |
| carry = d/10; | |
| } | |
| string strCarry; | |
| if( carry > 0 ) | |
| { | |
| stringstream css; //carry | |
| css << carry; | |
| strCarry = css.str(); | |
| } | |
| string temp = ss.str(); | |
| //has to be reversed as we add digits from right to left | |
| reverse(temp.begin(), temp.end()); | |
| temp = strCarry + temp; | |
| return temp; | |
| } | |
| int main() | |
| { | |
| int n; | |
| cin >> n; | |
| vector<string> numbers(n); | |
| int i; | |
| for( i = 0; i < n ; i++ ) | |
| { | |
| cin >> numbers[i]; | |
| } | |
| string sum = getSum( numbers ); | |
| cout << sum; | |
| return 0; | |
| } |
by