制約条件に従って2つの配列の要素を加算する方法を解説

この記事では、2つの配列の要素を加算し、その結果を別の配列に格納するという問題を扱います。ただし、単純な加算ではなく、以下のような制約条件に従う必要があります。

• 加算は、両方の配列の0番目のインデックス（先頭）から開始する
• 和が2桁以上の数になった場合は、桁ごとに分割し、各桁を順番に出力配列に格納する
• 長い方の入力配列に残った要素は、そのまま出力配列に格納する

それでは、処理の流れを理解するために、アルゴリズムから見ていきましょう。

アルゴリズム

addArrayConstraints(arr1, arr2)

開始
    空のベクトル out を定義する
    i := 0
    i が arr1.length と arr2.length の両方より小さい間、以下を繰り返す
        add := arr1[i] + arr2[i]
        add が1桁の数であれば
            add を out に挿入する
        そうでなければ
            add を桁ごとに分割し、各桁を順番に out に挿入する
    繰り返し終了
    arr1 に要素が残っている間、以下を繰り返す
        各要素を1桁ならそのまま、2桁以上なら分割して out に挿入する
    繰り返し終了
    arr2 に要素が残っている間、以下を繰り返す
        各要素を1桁ならそのまま、2桁以上なら分割して out に挿入する
    繰り返し終了
終了

C++での実装例

以下は、上記のアルゴリズムをC++で実装したコード例です。補助関数 splitDigit() は、数値を桁ごとに分割してベクターに格納する役割を担います。

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

void splitDigit(int num, vector<int> &out) { // 数値を桁ごとに分割してベクターに格納する
    vector<int> arr;
    while (num) {
        arr.insert(arr.begin(), num % 10);
        num = num / 10;
    }
    out.insert(out.end(), arr.begin(), arr.end());
}

void addArrayConstraints(int arr1[], int arr2[], int m, int n) {
    vector<int> out;
    int i = 0; // arr1 と arr2 の現在のインデックス
    while (i < m && i < n) {
        int add = arr1[i] + arr2[i];
        if (add < 10) // 1桁ならそのまま格納、そうでなければ分割して格納
            out.push_back(add);
        else
            splitDigit(add, out);
        i++;
    }
    while (i < m) // arr1 に残りの要素がある場合
        splitDigit(arr1[i++], out);
    while (i < n) // arr2 に残りの要素がある場合
        splitDigit(arr2[i++], out);
    for (int i = 0; i < out.size(); i++)
        cout << out[i] << " ";
}

int main() {
    int arr1[] = {9323, 8, 6, 55, 25, 6};
    int arr2[] = {38, 11, 4, 7, 8, 7, 6, 99};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    addArrayConstraints(arr1, arr2, n1, n2);
}

出力結果

9 3 6 1 1 9 1 0 6 2 3 3 1 3 6 9 9

処理の流れの解説

この例では、配列 arr1 = {9323, 8, 6, 55, 25, 6} と arr2 = {38, 11, 4, 7, 8, 7, 6, 99} を使用しています。

• 最初の要素同士の和は 9323 + 38 = 9361 となり、4桁の数なので 9、3、6、1 と桁ごとに分割されて格納されます。
• 次に 8 + 11 = 19 は 1、9 として格納され、以降も同様の処理が繰り返されます。
• インデックス6以降は arr1 の要素が尽きるため、arr2 に残った 6 と 99 が処理され、99 は 9、9 に分割されて出力配列に追加されます。

このように、制約条件に従って各桁を順番に格納していくことで、最終的な出力配列が得られます。計算量は両配列の長さと各要素の桁数に依存し、O((m + n) × d) となります（d は最大桁数）。