ตรวจสอบคู่ที่ให้ผลคูณเท่ากับ K ในเมทริกซ์ C++

ปัญหา

ให้เมทริกซ์ N×M และค่า K ตรวจสอบว่ามีคู่ของสมาชิกในเมทริกซ์ที่ให้ผลคูณเท่ากับ K หรือไม่

ตัวอย่าง: เมทริกซ์ 4×4 มีค่า 1-16, K=42 → คู่ (6, 7) ให้ 6×7=42

วิธีแก้ปัญหา: Hashing

คล้าย Linked List แต่วนทุกเซลล์ในเมทริกซ์:

1. สร้าง unordered_set เก็บค่าที่เจอแล้ว
2. วน i=0..N-1, j=0..M-1:
   • val = matrix[i][j]
   • ถ้า val ≠ 0 และ K % val == 0 และ (K/val) ใน set → พบคู่
   • เพิ่ม val ลง set
3. จบลูปไม่พบ → false

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

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

bool isPairPresent(const vector<vector<int>>& matrix, int K) {
    unordered_set<int> seen;
    int rows = matrix.size();
    int cols = matrix[0].size();
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int val = matrix[i][j];
            
            if (val != 0 && K % val == 0 && seen.count(K / val)) {
                cout << "Pair found at (" << i << "," << j << "): (" 
                     << val << ", " << K/val << ")" << endl;
                return true;
            }
            seen.insert(val);
        }
    }
    return false;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    
    int K = 42;
    if (isPairPresent(matrix, K))
        cout << "Pair is present" << endl;
    else
        cout << "NO PAIR EXIST" << endl;
    
    return 0;
}

ผลลัพธ์

Pair found at (1,2): (7, 6)
Pair is present

กรณีพิเศษ K = 0

ต้องมี 0 อยู่ในเมทริกซ์อย่างน้อย 1 ตัว และอีกตัวใดก็ได้ (เพราะ 0 × anything = 0)

if (K == 0) {
    bool hasZero = false;
    for (auto& row : matrix)
        for (int val : row)
            if (val == 0) { hasZero = true; break; }
    return hasZero && (rows * cols > 1); // ต้องมีอย่างน้อย 2 เซลล์
}

ความซับซ้อน

• เวลา: O(N×M) - ท่องเมทริกซ์ครั้งเดียว
• พื้นที่: O(N×M) - hash set เก็บค่าทั้งหมด
• สามารถปรับปรุงพื้นที่ได้ด้วย bitset ถ้าค่าอยู่ในช่วงจำกัด