Kiểm tra xem một cặp với sản phẩm đã cho có tồn tại trong Ma trận trong C ++ hay không

Chúng ta có một ma trận bậc N x M. Và một sản phẩm K. Nhiệm vụ là kiểm tra xem một cặp với sản phẩm đã cho có xuất hiện trong ma trận hay không.

Giả sử một ma trận giống như dưới đây -

Bây giờ nếu K là 42, thì có một cặp như (6, 7)

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng băm. Chúng ta sẽ tạo bảng băm bằng cách lấy tất cả các phần tử của ma trận. Chúng ta sẽ bắt đầu duyệt qua ma trận, trong khi duyệt, kiểm tra xem phần tử hiện tại của ma trận có chia hết cho tích đã cho hay không và khi tích K được chia cho phần tử hiện tại, thì số bị chia cũng sẽ xuất hiện trong bảng băm. Vì vậy, điều kiện bắt buộc là -

(k mod matrix [i, n]) là false và bảng băm có k / matrix [i, j]

Nếu có thì trả về true, nếu không thì chèn phần tử hiện tại vào bảng băm.

Nếu không tìm thấy cặp nào, hãy trả về false.

Ví dụ

#include <iostream>
#include <unordered_set>
#define N 4
#define M 4
using namespace std;
bool isPairPresent(int matrix[N][M], int K) {
   unordered_set<int> s;
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
         if ((K % matrix[i][j] == 0) && (s.find(K / matrix[i][j]) != s.end())) {
            return true;
         } else {
            s.insert(matrix[i][j]);
         }
      }
   }
   return false;
}
int main() {
   int matrix[N][M] = {{1, 2, 3, 4},
      {5, 6, 7, 8},
      {9, 10, 11, 12},
      {13, 14, 15, 16}};
      int k = 42;
   if (isPairPresent(matrix, k) == false)
      cout << "NO PAIR EXIST";
   else
      cout << "Pair is present";
}

Đầu ra

Pair is present