C++의 제품 배열 퍼즐?

여기서 우리는 배열과 관련된 한 가지 흥미로운 문제를 볼 것입니다. n개의 요소가 있는 배열이 있습니다. n개의 요소로 구성된 또 다른 배열을 만들어야 합니다. 그러나 두 번째 배열의 i번째 위치는 i번째 요소를 제외한 첫 번째 배열의 모든 요소의 곱을 유지합니다. 그리고 한 가지 제약 사항은 이 문제에서 나누기 연산자를 사용할 수 없다는 것입니다.

나눗셈 연산을 사용할 수 있다면 모든 요소의 곱을 구하고 첫 번째 배열의 i번째 요소를 나누어 두 번째 배열의 i번째 위치에 저장하면 이 문제를 쉽게 해결할 수 있습니다.

여기서 우리는 두 개의 개별 배열을 생성하여 이 문제를 해결합니다. 왼쪽과 오른쪽. left[i]는 array[i]를 제외한 array[i] 왼쪽에 있는 모든 요소의 곱을 보유하고 right[i]는 arr[i]를 제외한 arr[i] 오른쪽에 있는 모든 요소의 곱을 보유합니다. 이 솔루션은 O(n) 시간이 걸립니다. 하지만 추가 공간이 필요합니다.

알고리즘

제품배열(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