C ++の製品配列パズル（O（1）スペース）？

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

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

ここでは、1つの一時変数、つまり左部分と右部分の積を求めることによって解決しています。この値は最終的な配列に配置されます。したがって、余分なスペースは必要ありません。

アルゴリズム

productArray（arr、n）

begin
   define an array called res of size n
   fill the res array with 1
   temp := 1
   for i in range 1 to n, 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

例

#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;
   for(int i = 0; i<n; i++) {
      product[i] = 1; //set all elements of product as 1
   }
   for(int i = 0; i < n; i++) { //temp variable will hold product of elements on left excluding arr[i]
      product[i] = temp;
      temp *= arr[i];
   }
   temp = 1;
   for(int i = n - 1; i >= 0; i--) { //temp variable will hold product of elements on right excluding arr[i]
      product[i] *= temp;
      temp *= arr[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