C++の積配列パズル：除算を使わずに解くアルゴリズムを徹底解説

今回は配列に関する興味深い問題を取り上げます。n個の要素を持つ配列が与えられたとき、同じくn個の要素を持つ別の配列を作成します。ただし、新しい配列のi番目の位置には、元の配列のi番目の要素を除いた残りのすべての要素の積を格納する必要があります。さらに重要な制約として、除算（割り算）演算子を使用してはいけないという条件が課せられています。

もし除算を使えるのであれば、この問題は非常に簡単です。まず全要素の総積を求め、それを元の配列のi番目の要素で割ればよいだけだからです。しかし、除算が禁止されている場合、別のアプローチが必要になります。

解法のアイデア：左右からの累積積

ここでは、leftとrightという2つの補助配列を作成して問題を解きます。

• left[i]：arr[i]自身を含まない、その左側にあるすべての要素の積
• right[i]：arr[i]自身を含まない、その右側にあるすべての要素の積

こうすると、答えは res[i] = left[i] × right[i] として求められます。この手法の計算量はO(n)と効率的ですが、補助配列分の追加メモリが必要になる点に注意してください。

アルゴリズム

productArray(arr, n)

begin
    define two arrays left and right of size n
    define an array called res of size n
    the first element of left and last element of right is set as 1
    for i in range 1 to n, do
        left[i] = left[i-1] * arr[i-1]
    done
    for i in range n-1 down to 1, do
        right[i] = right[i+1] * arr[i+1]
    done
    for i in range 1 to n, do
        res[i] = left[i] * right[i];
    done
    return res
end

C++による実装例

#include<iostream>
using namespace std;
void printArray(int arr[], int n) {
    for(int i = 0; i<n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
void productArray(int arr[], int product[], int n) {
    // 左右の累積積用の配列を作成
    int *left = new int[sizeof(int)*n];
    int *right = new int[sizeof(int)*n];
    // left[0]とright[n-1]を1で初期化
    left[0] = right[n-1] = 1;
    // 左側の累積積を計算
    for(int i = 1; i<n; i++) {
        left[i] = left[i-1] * arr[i-1];
    }
    // 右側の累積積を計算
    for(int i = n-2; i>=0; i--) {
        right[i] = right[i+1] * arr[i+1];
    }
    // leftとrightを掛け合わせて結果を得る
    for(int i = 0; i<n; i++) {
        product[i] = left[i] * right[i];
    }
}
main() {
    int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
    int resArr[7];
    cout << "Initial Array: ";
    printArray(myArr, 7);
    productArray(myArr, resArr, 7);
    cout << "Final Array: ";
    printArray(resArr, 7);
}

実行結果

Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120

出力を見ると、たとえば最初の要素「5」に対する結果は「9072」になっています。これは 4 × 7 × 6 × 9 × 2 × 3 = 9072 であり、確かに自分自身を除いた他の要素すべての積になっていることが確認できます。

まとめ

この問題は、除算を使わずに「自分以外の要素の積」を求める典型的なテクニックの好例です。左方向と右方向からの累積積を組み合わせることで、O(n)の時間計算量で効率的に解くことができます。空間計算量をO(1)に抑えた最適化版も存在しますので、興味のある方はぜひ調べてみてください。