[5. high precision subtraction]

High precision subtraction

Ideas ：

• Large integer storage （ Use arrays to store ）, It is still stored in the array in reverse order
• Subtract decimals from large numbers , This is more convenient
• Consider borrowing , borrow 1 Add 10

step ：

1. take A and B Stored in the array in reverse order .
2. hypothesis A and B Two numbers , First judgement A - B Value . Always subtract decimals from large numbers 【 for example A >= B, The result is A - B, If it is A <= B, Then the result is -(B - A)】
3. Judge A0 - B0 - t >= 0 . At this point, there is no need to borrow A0 - B0 - t, If A0 - B0 - t < 0, You need to borrow A0 - B0 + 10 - t( there t Is to judge whether to borrow , If you borrow, you will subtract the borrowed digits , If not, subtract 0)
4. Remove leading 0 . The so-called leading zero , There are data like this 01234, This 0 It's actually unnecessary .
5. take C Number in , Print out in reverse order , Because it is stored upside down .

give an example

39246 - 1965 = 37281

Code

#include <iostream>
using namespace std;
#include <vector>

bool cmp(vector<int> &A, vector<int>&B)
{
     
    if (A.size() != B.size())  return A.size() > B.size();      // When the length of two numbers is not equal 
    for (int i = A.size() - 1; i >= 0; i --)                    // Each bit of equal length is compared in turn 
    {
     
        if (A[i] != B[i]) return A[i] > B[i]; 
    }
    return true;                                                // The two numbers are exactly equal 
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
     
    vector<int> C;
    for (int t = 0, i = 0; i < A.size(); i ++)                  // The front has made A Always the largest ,t For borrow 
    {
     
        t = A[i] - t;
        if (i < B.size()) t -= B[i];                            //i Has more than B It's the number of digits , At this point, there is no need to reduce 
        C.push_back((t + 10) % 10);                              // Combined the two situations ,t >= 0 , The amount deposited at this time is t, If t < 0, In this case, borrowing is required for storage  
   
        if (t < 0) t = 1;                                        //t < 0  Equivalent to borrowing , At this point, you need to subtract from the number borrowed 1
        else t = 0;
    }
    
    while (C.size() > 1 && C.back() == 0) C.pop_back();         // Remove the lead 0, If it turns out to be 01234, Remove the beginning at this time 0
    return C;
    
}

int main()
{
     
    string a, b;
    vector<int> A, B;
    cin >> a >> b;                       //a = '123456'
    
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');  //A =[6,5,4,3,2,1] -'0' Is to change a string into an integer 
    for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
    
    if (cmp(A, B))
    {
     
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    }
    else
    {
     
        
      
        auto C = sub(B, A);
        printf ("-");
        for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    }
    return 0;
}