C++의 제품 배열 퍼즐(O(1) Space)?

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

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

여기서 우리는 하나의 임시 변수, 즉 왼쪽 부분과 오른쪽 부분의 곱을 찾는 것으로 해결합니다. 이 값은 최종 배열에 배치됩니다. 따라서 추가 공간이 필요하지 않습니다.

알고리즘

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