C++で2つの大きな数の合計を求める方法

この問題では、2つの大きな数を表す文字列が与えられます。私たちのタスクは、これら2つの大きな数の合計を求めるプログラムを作成することです。

大きな数は int や long long などの標準の整数型では表現できないほど大きくなるため、数値を文字列として受け取り、桁ごとに演算を行う手法が有効です。

問題を理解するための例

入力: number1 = "341299123919"
number2 = "52413424"
出力: 341351537343

解決のアプローチ

この問題を解くには、両方の文字列を1の位（末尾）から先頭に向かって走査します。各桁を1桁ずつ加算し、合計が10を超えた分は繰り上がり（carry）として次の桁へ伝播させます。計算結果の各桁は、合計を格納する文字列に順次追加していきます。

アルゴリズム

sum = ""、carry = 0 で初期化する。
ステップ1: 短い方の数の末尾から先頭に向かってループする。
ステップ1.1: intSum = number1[i] + number2[i] + carry（数値として計算）
ステップ1.2: carry = intSum / 10 とし、sum に intSum % 10 を追加する。
ステップ2: 長い方の数の残りの桁に対して同じ処理を繰り返す。
ステップ3: 最後に繰り上がりが残っていれば sum に追加する。
ステップ4: sum を反転して返す。

実装例

このソリューションの動作を示すプログラムは以下のとおりです。

#include<bits/stdc++.h>
using namespace std;
string addBigNumbers(string number1, string number2) {
    if (number1.length() > number2.length())
        swap(number1, number2);
    string sum = "";
    int len1 = number1.length();
    int len2 = number2.length();
    int digitDiff = len2 - len1;
    int carry = 0;
    int intSum;
    for (int i = len1 - 1; i >= 0; i--) {
        intSum = ((number1[i]-'0') + (number2[i+digitDiff]-'0') + carry);
        sum.push_back(intSum%10 + '0');
        carry = intSum/10;
    }
    for (int i = digitDiff - 1; i >= 0; i--) {
        intSum = ((number2[i]-'0') + carry);
        sum.push_back(intSum%10 + '0');
        carry = intSum/10;
    }
    if (carry)
        sum.push_back(carry+'0');
    reverse(sum.begin(), sum.end());
    return sum;
}
int main() {
    string number1 = "235235823852";
    string number2 = "45230820348";
    cout<<"Sum of two large numbers is "<<addBigNumbers(number1, number2);
    return 0;
}

出力

Sum of two large numbers is 280466644200

このように、文字列として与えられた大きな数でも、桁ごとの加算と繰り上がりの管理を適切に行うことで、標準の整数型の制限を受けずに正確な合計を求めることができます。各桁を1回ずつ処理するため、計算量は O(max(len1, len2)) となり、非常に効率的です。