C ++の製品配列パズル？

ここでは、配列に関連する1つの興味深い問題を確認します。 n個の要素を持つ配列があります。 n個の要素の別の配列を作成する必要があります。ただし、2番目の配列のi番目の位置は、i番目の要素を除く最初の配列のすべての要素の積を保持します。そして、1つの制約は、この問題では除算演算子を使用できないことです。

除算、演算を使用できれば、すべての要素の積を取得し、最初の配列のi番目の要素を除算して、2番目の配列のi番目の場所に格納することで、この問題を簡単に解決できます。

ここでは、2つの別々の配列を作成することでこれを解決しています。左右。 left [i]は、array[i]を除くarray[i]の左側にあるすべての要素の積を保持し、right [i]は、arr[i]を除くarr[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

例

#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) {
   //create left right array
   int *left = new int[sizeof(int)*n];
   int *right = new int[sizeof(int)*n];
   //set the first element of left[] and last element of right[] as 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];
   }
   //get product array using left and right array
   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