Algorithm daily practice — day 81: high-precision addition

Make writing a habit together! This is the 16th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I. Problem description

Given two positive integers (excluding leading 0), calculate their sum.

1≤ Integer length ≤1000001≤ Integer length ≤1000001≤ Integer length ≤100000

Title link: High precision addition.

Two, the title requirements

Sample 1

Input: 12 23 Output: 35Copy the code

The sample 2

Input: 123 98 Output: 221Copy the code

inspection

1. High precision 2. The recommended time is 15~30minCopy the code

Third, problem analysis

The value of a string can range from 1 to 65400 characters. After the string input, we need to evaluate the number, so char->int, through -‘0’.

We’re going to store each digit in an array, and before we do that, let’s think about the question, do we store it forward or backward?

For example, which of the following is used to store the number 75842:

Subscript: 0 1 2 3 4 Number: 7 5 8 4 2 Subscript: 4 3 2 1 0 Number: 7 5 8 4 2Copy the code

Definitely use the second one! The first one, you see, can the top carry forward, and then go forward is -1.

For the addition rule, the use of primary school learned the corresponding digit addition, full 10 into 1 on the line.

Four, coding implementation

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> add(vector<int> &a, vector<int> &b)  
{
    int i,k=0;// The initial carry is 0
    vector<int>c;
    for(i=0; i<a.size()||i<b.size(a); i++)// Within the range
    {
        if(i<a.size()) k+=a[i];
        if(i<b.size()) k+=b[i];
        c.push_back(k%10);/ / 10 add %
        k=k/10;/ / carry
    }
    if(k)// Make sure the remaining carry is added
       c.push_back(k); 
    return c;
}
int main(a)
{
    string s1,s2;// String storage
    int i;
    cin>>s1>>s2;
    vector<int>a,b,c;
    for(i=s1.size(a)- 1; i>=0; i--)// The string is converted to a number and stored in reverse order
        a.push_back(s1[i]-'0');
    for(i=s2.size(a)- 1; i>=0; i--)// The string is converted to a number and stored in reverse order
        b.push_back(s2[i]-'0');
    c=add(a, b);// The addition rule
    for (i=c.size(a)- 1; i>=0; i--)// Output the result
        cout<<c[i];
    return 0;
}
Copy the code

V. Test results