Một câu đố mảng sản phẩm (O (1) Space) trong C ++?

Ở đây chúng ta sẽ thấy một vấn đề thú vị liên quan đến mảng. Có một mảng với n phần tử. Chúng ta phải tạo một mảng khác gồm n phần tử. Nhưng vị trí thứ i của mảng thứ hai sẽ chứa tích của tất cả các phần tử của mảng đầu tiên ngoại trừ phần tử thứ i. Và một hạn chế là chúng ta không thể sử dụng toán tử chia trong bài toán này. Chúng tôi phải giải quyết vấn đề này tại chỗ mà không cần sử dụng thêm bất kỳ khoảng trống nào.

Nếu chúng ta có thể sử dụng phép chia, phép toán, chúng ta có thể dễ dàng giải quyết vấn đề này, bằng cách lấy tích của tất cả các phần tử, sau đó chia phần tử thứ i của mảng đầu tiên và lưu nó vào vị trí thứ i của mảng thứ hai.

Ở đây chúng ta đang giải quyết bằng cách lấy một biến tạm thời, đó là tìm tích của phần bên trái và phần bên phải. Giá trị này sẽ được đặt vào mảng cuối cùng. Vì vậy, nó sẽ không tốn thêm dung lượng.

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120