Kiểm tra cặp có tích bằng K trong danh sách liên kết C++

Cho danh sách liên kết và số K. Kiểm tra có cặp nào cho tích = K không. In ra cặp nếu có.

Ví dụ: {2, 4, 8, 12, 15}, K=16 → cặp (2, 8).

Giải thuật (Hashing)

1. Tạo unordered_set lưu các phần tử đã duyệt
2. Duyệt danh sách: với phần tử current, nếu K % current == 0 và K/current có trong set → tìm thấy
3. Thêm current vào set, tiếp tục

Ví dụ minh họa

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

class Node {
public:
    int data;
    Node* next;
};

void append(Node** start, int key) {
    Node* new_node = new Node;
    new_node->data = key;
    new_node->next = *start;
    *start = new_node;
}

bool isPairPresent(Node* start, int K) {
    unordered_set<int> s;
    Node* p = start;
    while (p != NULL) {
        int current = p->data;
        if ((K % current == 0) && (s.find(K / current) != s.end())) {
            cout << current << " " << K / current;
            return true;
        }
        s.insert(p->data);
        p = p->next;
    }
    return false;
}

int main() {
    Node* start = NULL;
    int arr[] = {2, 4, 8, 12, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    for (int i = 0; i < n; i++) append(&start, arr[i]);
    if (!isPairPresent(start, 16)) cout << "KHONG CO CAP";
}

Kết quả

2 8