C++で解く積配列パズル ― 除算なし・O(1)の追加メモリで実現する方法

問題の概要

今回は配列に関する興味深いパズルを取り上げます。n個の要素を持つ配列が与えられたとき、同じくn個の要素を持つ別の配列を作成します。ただし、新しい配列のi番目の要素には、元の配列のi番目の要素を除いた残りすべての要素の積を格納する必要があります。

この問題には次の2つの制約があります。

• 除算演算子（/）を使用してはならない
• 出力用の配列以外、追加のメモリ領域はO(1)に抑えること

もし除算が許されるなら話は簡単です。配列全体の積を事前に計算しておき、それを各要素で割った値を順に格納すればよいからです。しかし、配列に0が含まれると除算が使えない、積が大きくなるとオーバーフローの恐れがあるといった理由から、実際には除算に頼らない解法が求められます。

解法のポイント：左側の積と右側の積に分ける

ここでは一時変数を1つだけ使って問題を解きます。鍵となる考え方は、「ある要素より左側にある要素の積」と「右側にある要素の積」を分けて管理することです。

1. まず配列を左から右へ走査し、res[i] に「arr[i] より左側の要素の積」を格納します。
2. 次に配列を右から左へ走査し、res[i] に「arr[i] より右側の要素の積」を掛け合わせます。

この2段階の処理により、res[i] には arr[i] 以外のすべての要素の積が完成します。結果を格納する配列 res 自体を作業領域として再利用するため、追加のメモリは一切不要です。

アルゴリズム

productArray(arr, n)

begin
    define an array called res of size n
    fill the res array with 1
    temp := 1
    for i in range 0 to n-1, do
        res[i] := temp
        temp := temp * arr[i]
    done
    for i in range n-1 down to 0, do
        res[i] := res[i] * temp
        temp := temp * arr[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 temp = 1;
    // すべての要素を1で初期化
    for (int i = 0; i < n; i++) {
        product[i] = 1;
    }
    // temp には arr[i] を除く「左側」の要素の積が入る
    for (int i = 0; i < n; i++) {
        product[i] = temp;
        temp *= arr[i];
    }
    temp = 1;
    // temp には arr[i] を除く「右側」の要素の積が入る
    for (int i = n - 1; i >= 0; i--) {
        product[i] *= temp;
        temp *= arr[i];
    }
}

int 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);
    return 0;
}

実行結果

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

例えば最初の要素 9072 は、5以外の要素 4 × 7 × 6 × 9 × 2 × 3 の積になっています。同様に、各位置にはその要素自身を除いた積が正しく格納されていることが確認できます。

計算量

• 時間計算量：O(n) ― 配列を前後から1回ずつ、合計2回走査するだけです。
• 空間計算量：O(1) ― 出力配列を除けば、使用するのは一時変数 temp のみです。