주어진 제품과의 쌍이 C++의 Matrix에 존재하는지 확인

우리는 N x M 차수의 행렬이 하나 있고 제품 ​​K가 있습니다. 작업은 주어진 제품과의 쌍이 행렬에 존재하는지 여부를 확인하는 것입니다.

행렬이 아래와 같다고 가정 -

이제 K가 42이면 (6, 7)과 같은 쌍이 있습니다.

이 문제를 해결하기 위해 해싱을 사용합니다. 행렬의 모든 요소를 ​​가져와서 해시 테이블을 생성합니다. 우리는 행렬 순회를 시작할 것이고, 순회하는 동안 행렬의 현재 요소가 주어진 곱으로 나눌 수 있는지 확인하고 곱 K를 현재 요소로 나눌 때 배당금도 해시 테이블에 표시됩니다. 따라서 필수 조건은 다음과 같습니다. -

(k mod matrix[i, n])은 거짓이고 해시 테이블에는 k/matrix[i, j]

존재하면 true를 반환하고, 그렇지 않으면 현재 요소를 해시 테이블에 삽입합니다.

쌍을 찾지 못하면 false를 반환합니다.

예

#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";
}

출력

Pair is present