2. arrayからproduct羅列

問題

整数を要素にもつarrayから、どれか１つの要素を除いた積のarrayを出力する。 ただし、割り算は使えない。

考え方

arrayの長さをNとする。 単純に全て計算するとの時間計算量がかかる。

出来るだけ前の値を用いて計算したい。 前の変数までの積と次の変数の積を記録していく。この操作を、前から(f[])と後ろから(b[])行う。 その後、f[i] * b[i]を計算すると、ちょうどi番目の変数を省いた積になっている。

時間計算量、空間計算量ともにとなる。

N = 3の時

	array[0]	array[1]	array[2]
前から	1	array[0]	array[0]*array[1]
後ろから	array[1]*array[2]	array[2]	1
積	array[1]*array[2]	array[0]*array[2]	array[0]*array[1]

コード例

#include <iostream>
#include <memory>

int* list_prod(int n, int array[]){
    int feed[n], back[n];
    int *prod = (int*)std::malloc(n*sizeof(int));
    int i;
    feed[0] = 1;
    back[n-1] = 1;
    for(i=0; i<n-1; i++){
        feed[i+1] = feed[i] * array[i];
    }
    for(i=n-1; i>0; i--){
        back[i-1] = back[i] * array[i];
    }
    for(i=0; i<n; i++){
        prod[i] = feed[i]*back[i];
    }
    return prod;
}

int main(void){
    int n = 5;
    int i;
    int array[n] = {1, 2, 3, 4, 5};
    int *ans;
    ans = list_prod(n, array);
    for(i=0; i<n; i++){
        std::cout << ans[i] << std::endl;
    }
    return 0;
}