ปริศนาอาร์เรย์ผลคูณ (Product Array Puzzle) ใน C++

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

ถ้าใช้การหารได้ จะง่าย: หาผลคูณทั้งหมด แล้วหารด้วยสมาชิกที่ i และเก็บไว้ที่ตำแหน่ง i

ที่นี่เราแก้โดยสร้างอาร์เรย์แยกสองตัวคือ left และ right left[i] จะเก็บผลคูณของสมาชิกทั้งหมดทางซ้ายของ arr[i] ไม่รวม arr[i] ส่วน right[i] จะเก็บผลคูณทางขวา วิธีนี้ใช้เวลา O(n) แต่ต้องการพื้นที่เพิ่ม

อัลกอริทึม

productArray(arr, n)

เริ่มต้น
  กำหนดอาร์เรย์ left และ right ขนาด n
  กำหนดอาร์เรย์ res ขนาด n
  ตั้งค่า left[0] และ right[n-1] เป็น 1
  สำหรับ i ในช่วง 1 ถึง n ทำ
    left[i] = left[i-1] * arr[i-1]
  จบลูป
  สำหรับ i ในช่วง n-1 ลงมาที่ 1 ทำ
    right[i] = right[i+1] * arr[i+1]
  จบลูป
  สำหรับ i ในช่วง 1 ถึง n ทำ
    res[i] = left[i] * right[i]
  จบลูป
  คืนค่า res
สิ้นสุด

ตัวอย่างโค้ด

#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) {
    // สร้างอาร์เรย์ left และ right
    int *left = new int[sizeof(int)*n];
    int *right = new int[sizeof(int)*n];
    // ตั้งค่า left[0] และ right[n-1] เป็น 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];
    }
    // หาอาร์เรย์ผลคูณจาก left และ right
    for (int i = 0; i < n; i++) {
        product[i] = left[i] * right[i];
    }
}

int 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);
    return 0;
}

ผลลัพธ์

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