ปริศนาอาร์เรย์ผลิตภัณฑ์ (O (1) Space) ใน C ++?

ที่นี่เราจะเห็นปัญหาหนึ่งที่น่าสนใจเกี่ยวกับอาร์เรย์ มีอาร์เรย์ที่มีองค์ประกอบ n เราต้องสร้างอาร์เรย์ขององค์ประกอบ n อีกชุดหนึ่ง แต่ตำแหน่งที่ i ของอาร์เรย์ที่สองจะเก็บผลคูณขององค์ประกอบทั้งหมดของอาร์เรย์แรก ยกเว้นองค์ประกอบที่ i และข้อจำกัดอย่างหนึ่งคือเราไม่สามารถใช้ตัวดำเนินการหารในปัญหานี้ได้ เราต้องแก้ปัญหานี้แทนโดยไม่ต้องใช้ช่องว่างเพิ่มเติม

ถ้าเราสามารถใช้การหาร การดำเนินการ เราก็สามารถแก้ปัญหานี้ได้ง่ายๆ โดยหาผลคูณขององค์ประกอบทั้งหมด จากนั้นแบ่งองค์ประกอบที่ i ของอาร์เรย์ที่หนึ่งและจัดเก็บไว้ในตำแหน่งที่ i ของอาร์เรย์ที่สอง

เรากำลังแก้ไขโดยใช้ตัวแปร temp ตัวเดียว นั่นคือ การหาผลคูณของส่วนซ้ายและส่วนขวา ค่านี้จะถูกวางลงในอาร์เรย์สุดท้าย จึงไม่เปลืองเนื้อที่

อัลกอริทึม

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