C言語で解く積配列パズル（Product Array Puzzle）とは？

配列（Array）とは、同じデータ型の要素を格納するためのコンテナです。積配列パズル（Product Array Puzzle）は、配列の全要素の積を扱う古典的なアルゴリズム問題の一つです。

このパズルでは、各要素について「その要素自身を除いた、残りのすべての要素の積」を計算します。ただし、次の2つの条件が課せられます。

• 除算演算子（/）を使用してはならない
• 結果は別の配列に格納すること

解法の考え方

この問題は、「左側の要素の積」と「右側の要素の積」という2つの配列を作成することで効率的に解けます。手順は以下の通りです。

1. left[i]：インデックス i より左側にあるすべての要素の積を求める
2. right[i]：インデックス i より右側にあるすべての要素の積を求める
3. prod[i] = left[i] * right[i]：両者を掛け合わせることで、自身を除いた積が得られる

この手法を使えば、除算を行わずとも時間計算量 O(n) で答えを求めることができます。

C言語での実装例

#include<stdio.h>
#include<stdlib.h>
void productfind(int arr[], int n) {
    int *left = (int *)malloc(sizeof(int)*n);
    int *right = (int *)malloc(sizeof(int)*n);
    int *prod = (int *)malloc(sizeof(int)*n);
    int i, j;
    left[0] = 1;
    right[n-1] = 1;
    for(i = 1; i < n; i++)
        left[i] = arr[i-1]*left[i-1];
    for(j = n-2; j >=0; j--)
        right[j] = arr[j+1]*right[j+1];
    for (i = 0; i < n; i++)
        prod[i] = left[i] * right[i];
    for (i = 0; i < n; i++)
        printf("%d ", prod[i]);
    return;
}
int main() {
    int arr[] = {10, 3, 5, 6, 2};
    printf("The array is : \n");
    int n = sizeof(arr)/sizeof(arr[0]);
    for(int i = 0;i < n; i++){
        printf("%d ",arr[i]);
    }
    printf("\nThe product array is: \n");
    productfind(arr, n);
}

実行結果

The array is :
10 3 5 6 2
The product array is:
180 600 360 300 900

処理の流れを確認

入力配列が {10, 3, 5, 6, 2} の場合、処理は次のように進みます。

• 例えば prod[0] は「左側の積（1）× 右側の積（3×5×6×2=180）」＝ 180
• prod[2] は「左側の積（10×3=30）× 右側の積（6×2=12）」＝ 360

このように、各位置に対して自身を含まない左右の積を掛け合わせるだけで、除算なしに正しい結果が得られます。なお、補助配列として left と right を使用しているため、空間計算量は O(n) となります。