Product Array Puzzle ใน C

สร้างอาร์เรย์ผลคูณที่ prod[i] = ผลคูณของทุก elements ยกเว้น arr[i] ห้ามใช้หาร

วิธีแก้: Prefix/Suffix Products

1. left[i] = ผลคูณ arr[0]...arr[i-1]
2. right[i] = ผลคูณ arr[i+1]...arr[n-1]
3. prod[i] = left[i] × right[i]

ตัวอย่าง

arr = {10, 3, 5, 6, 2}
prod = {180, 600, 360, 300, 900}

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

#include <stdio.h>
#include <stdlib.h>

void productArray(int arr[], int n) {
    int *left = malloc(n * sizeof(int));
    int *right = malloc(n * sizeof(int));
    int *prod = malloc(n * sizeof(int));

    left[0] = 1;
    for (int i = 1; i < n; i++) left[i] = arr[i-1] * left[i-1];

    right[n-1] = 1;
    for (int i = n-2; i >= 0; i--) right[i] = arr[i+1] * right[i+1];

    for (int i = 0; i < n; i++) prod[i] = left[i] * right[i];

    for (int i = 0; i < n; i++) printf("%d ", prod[i]);
    free(left); free(right); free(prod);
}

int main() {
    int arr[] = {10, 3, 5, 6, 2};
    int n = 5;
    productArray(arr, n);
    return 0;
}

ผลลัพธ์

180 600 360 300 900