【C++】片方の数値が桁の配列として表現された2つの数値の合計を求める方法

この問題では、2つの数値が与えられ、そのうちの1つは桁（けた）の配列として表現されています。ここでの課題は、片方の数値が桁の配列として与えられている場合に、2つの数値の合計を正しく求めるプログラムを作成することです。

問題を理解するための例

入力: n = 213, m[] = {1, 5, 8}
出力: 371
説明: 213 + 158 = 371

解法のアプローチ

この問題は、筆算と同じ要領で「桁ごとの加算」を行うことで解くことができます。具体的な手順は以下の通りです。

• 数値 n の最下位桁（1の位）を、配列の末尾（(size-1)番目）の要素に加算します。
• 加算結果が10以上になった場合は繰り上がり（キャリー）を発生させ、次の桁の加算に引き継ぎます。
• この処理を配列の先頭に到達するまで繰り返します。

アルゴリズムの手順

1. 繰り上がりを保持する変数 carry を 0 で初期化します。
2. 配列の末尾から先頭に向かってループ処理を行います。
3. 各反復で「n の最下位桁 ＋ 配列要素 ＋ carry」を計算します。
4. 合計を10で割った余りをその桁の値として配列に格納し、商を新しい carry とします。
5. n を10で割って、次の桁へ処理を進めます。

実装例

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

#include <iostream>
using namespace std;

void addNumbers(int n, int size, int *m){
    int carry = 0;
    int sum = 0;
    for(int i = size-1; i >= 0; i--){
        sum = (n%10) + m[i] + carry;
        n /= 10;
        carry = sum/10;
        m[i] = sum%10;
    }
}

int main() {
    int n = 679;
    int m[] = {1, 9, 5, 7, 1, 9};
    int size = sizeof(m)/sizeof(m[0]);
    cout<<"The sum of two numbers where one number is represented as array of digits is ";
    addNumbers(n, size, m);
    for(int i = 0; i < size; i++)
        cout<<m[i];
}

出力

The sum of two numbers where one number is represented as array of digits is 196398

出力結果から、679 ＋ 195719 ＝ 196398 と正しく合計が求められていることが確認できます。

注意点

この実装では、配列のサイズが結果の桁数を十分にカバーできることを前提としています。最終的に繰り上がりが残るケースや、n の桁数が配列のサイズを上回るケースに対応するには、より大きな配列を用意して結果を格納するなど、追加の処理が必要になる点に注意してください。