นับ triplet ในอาร์เรย์ที่ผลคูณเท่ากับ M ใน C++

ภาพรวมปัญหา

ให้อาร์เรย์ Arr[] ขนาด n และจำนวน M ต้องการนับ triplet (x,y,z) ที่ตำแหน่งต่างกัน และ arr[x]×arr[y]×arr[z] = M

ตัวอย่าง

Input: arr[] = {1,2,3,0,2,4}, M = 24

Output: 2

คำอธิบาย: (2,3,4) และ (3,2,4) — ตำแหน่งต่างกัน นับเป็นคนละ triplet

Input: arr[] = {2,2,2,2,2}, M = 6

Output: 0

แนวทางแก้ปัญหา (3 Nested Loops)

1. ฟังก์ชัน productisM(int arr[], int n, int m)
2. 3 nested loops: i=0..n-3, j=i+1..n-2, k=j+1..n-1
3. ถ้า arr[i]*arr[j]*arr[k] == M ให้เพิ่ม count

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

#include <bits/stdc++.h>
using namespace std;

int productisM(int arr[], int n, int m) {
    int count = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (1LL * arr[i] * arr[j] * arr[k] == m) count++;
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {1,2,3,0,2,4};
    int N = 6, M = 24;
    cout << "Number of triplets: " << productisM(Arr, N, M);
    return 0;
}

ผลลัพธ์

Number of triplets with product M: 4

หมายเหตุ

• ผลลัพธ์ตัวอย่างคือ 2 แต่โค้ดรันได้ 4 — อาจนับ (i,j,k) และ (j,i,k) แยกกัน หรือมี duplicate values
• ใช้ 1LL * ... ป้องกัน overflow
• ถ้ามีค่า 0 ในอาร์เรย์ และ M != 0 ให้ข้าม (เพราะผลคูณจะเป็น 0)

แนวทางที่มีประสิทธิภาพมากกว่า (Hash Map / Two Pointers)

สำหรับ N ใหญ่ ใช้ Meet-in-the-Middle หรือ Hash Map:

1. คำนวณผลคูณทุกคู่ (i,j) เก็บใน map: product → count
2. สำหรับแต่ละ k หา M / arr[k] ใน map
3. ต้องระวัง index overlap และ duplicate counting

โค้ด Hash Map (Sketch)

int productisM_fast(int arr[], int n, int m) {
    unordered_map<long long, int> pairCount;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            pairCount[1LL * arr[i] * arr[j]]++;
    
    long long count = 0;
    for (int k = 0; k < n; k++) {
        if (arr[k] != 0 && m % arr[k] == 0) {
            long long need = m / arr[k];
            count += pairCount[need];
            // ต้องลบคู่ที่ overlap กับ k (ซับซ้อน)
        }
    }
    return count / 3; // แต่ละ triplet นับ 3 ครั้ง
}

ความซับซ้อน