ปริศนาอาร์เรย์ผลคูณ (O(1) Space) ใน C++

โจทย์เดียวกันกับ Product Array Puzzle แต่ต้องแก้แบบ in-place โดยไม่ใช้พื้นที่เพิ่มเติม และห้ามใช้การหาร

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

อัลกอริทึม

productArray(arr, n)

เริ่มต้น
  กำหนดอาร์เรย์ res ขนาด n
  เติมค่า res ด้วย 1
  temp := 1
  สำหรับ i ในช่วง 1 ถึง n ทำ
    res[i] := temp
    temp := temp * arr[i]
  จบลูป
  สำหรับ i ในช่วง n-1 ลงมาที่ 0 ทำ
    res[i] = res[i] * temp
    temp := temp * arr[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) {
    int temp = 1;
    for (int i = 0; i < n; i++) {
        product[i] = 1; // ตั้งค่าทุกตัวเป็น 1
    }
    for (int i = 0; i < n; i++) { // temp เก็บผลคูณด้านซ้าย ไม่รวม arr[i]
        product[i] = temp;
        temp *= arr[i];
    }
    temp = 1;
    for (int i = n - 1; i >= 0; i--) { // temp เก็บผลคูณด้านขวา ไม่รวม arr[i]
        product[i] *= temp;
        temp *= arr[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