两个大数相减

题目描述

给定两个正整数，计算它们的差，计算结果可能为负数。

输入格式
共两行，每行包含一个整数。

输出格式
共一行，包含所求的差。

数据范围
1≤整数长度≤105

输入样例

32
11

输出样例

21

时间复杂度 O(n)

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef vector<int> vec;

bool cmp ( const vec& a, const vec& b ) {
    const int na = a.size ( ), nb = b.size ( );
    if ( na != nb ) return na > nb;   // 两数的数位长度不等

    for ( int i = na - 1; i >= 0; i-- ) // 两数的数位长度相等
        if ( a [ i ] != b [ i ] )       // 两数对应数位不等
            return a [ i ] > b [ i ];
    return true;
}

vec sub ( const vec &a, const vec& b ) {
    const int na = a.size ( ), nb = b.size ( );
    vec c;
    // 数位上的数字都考虑为非负数，范围[0, 9]
    // 数位上的最小差为：0 - 9， 最大为：9 - 0
    int sum = 0;   // -9 <= sum <= 9
    for ( int i = 0; i < na ; i++ ) {
        sum = a [ i ] - sum;     
        if ( i < nb ) sum -= b [ i ];
         // 如果，数位上的数字是负数。为了使之为正。所以加10再取模
        c.push_back ( ( sum + 10 ) % 10 ); 
        // 根据数位差的正负，确定是否借位
        ( sum < 0 ) ? sum = 1 : sum = 0;   
    }
    // 由于是倒序计算，可能有前导0被保存在结果中
    // 结果位数大于一并且前导0存在
    while ( c.size ( ) > 1 && c.back ( ) == 0 ) c.pop_back();
    return c;
}

void init ( vec& v, string& s ) {
    cin >> s;
    const int n = s.size ( );
    // 注意：字符转数字需减去字符'0'
    for ( int i = n - 1; i >= 0; i-- ) v.push_back ( s [ i ] - '0' );
}

void show ( const vec& v ) {
    const int n = v.size ( );
    for ( int i = n - 1; i >= 0; i-- ) cout << v [ i ];
    cout << endl;
}

void solve ( const vec& a, const vec& b ) {
    vec c;
    if ( cmp ( a, b ) )  c = sub ( a, b );
    else {
        c = sub ( b, a );
        cout << '-';
    }
    show(c);
}

int main ( ) {
    string s1, s2;
    vec a, b;
    init ( a, s1 ), init ( b, s2 );
    solve ( a, b );
    return 0;
}