Check if a pair with given product exists in a Matrix
Given an NxM matrix and a product K. The task is to check if a pair with the given product exists in the matrix or not.
Examples:
Input: mat[N][M] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}; K = 42 Output: YES Input: mat[N][M] = {{1, 2, 3, 4}, {5, 6, 7, 8}}; K = 150 Output: NO
Approach:
- Take a hash to store all elements of the matrix in the hash.
- Start traversing through the matrix, and while traversing check if the current element of the matrix is divisible by the given product and when the product K is divided by the current element, the dividend obtained is also present in the hash.
That is,
(k % mat[i][j] == 0) && (mp[k / mat[i][j]] > 0)
- If present, then return true, else insert current elements into the hash.
- If all elements of the matrix are traversed and no pair is found, return false.
Below is the implementation of the above approach:
C++
// CPP code to check for pair with given product // exists in the matrix or not #include <bits/stdc++.h> using namespace std; #define N 4 #define M 4 // Function to check if a pair with given // product exists in the matrix bool isPairWithProductK( int mat[N][M], int k) { // hash to store elements unordered_set< int > s; // looping through elements // if present in the matrix // return true, else push // the element in matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { if ((k % mat[i][j] == 0) && (s.find(k / mat[i][j]) != s.end())) { return true ; } else { s.insert(mat[i][j]); } } } return false ; } // Driver code int main() { // Input matrix int mat[N][M] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // given product int k = 42; if (isPairWithProductK(mat, k)) { cout << "YES" << endl; } else cout << "NO" << endl; return 0; } |
Java
// Java code to check for pair with given product // exists in the matrix or not import java.util.*; class GFG { static final int N= 4 ; static final int M= 4 ; // Function to check if a pair with given // product exists in the matrix static boolean isPairWithProductK( int mat[][], int k) { // hash to store elements Set<Integer> s= new HashSet<Integer>(); // looping through elements // if present in the matrix // return true, else push // the element in matrix for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { if ((k % mat[i][j] == 0 ) && s.contains(k / mat[i][j])) { return true ; } else { s.add(mat[i][j]); } } } return false ; } // Driver code public static void main(String [] args) { // Input matrix int mat[][] = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 9 , 10 , 11 , 12 }, { 13 , 14 , 15 , 16 } }; // given product int k = 42 ; if (isPairWithProductK(mat, k)) { System.out.println( "YES" ); } else System.out.println( "NO" ); } // This code is contributed by ihritik } |
Python 3
# Python 3 code to check for pair with # given product exists in the matrix or not N = 4 M = 4 # Function to check if a pair with # given product exists in the matrix def isPairWithProductK(mat, k): # hash to store elements s = [] # looping through elements if present # in the matrix return true, else push # the element in matrix for i in range (N) : for j in range (M): if ((k % mat[i][j] = = 0 ) and (k / / mat[i][j]) in s): return True else : s.append(mat[i][j]) return False # Driver code if __name__ = = "__main__" : # Input matrix mat = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ], [ 13 , 14 , 15 , 16 ]] # given product k = 42 if (isPairWithProductK(mat, k)): print ( "YES" ) else : print ( "NO" ) # This code is contributed by ita_c |
C#
// C# code to check for pair with given product // exists in the matrix or not using System; using System.Collections.Generic; class GFG { static readonly int N = 4; static readonly int M = 4; // Function to check if a pair with given // product exists in the matrix static bool isPairWithProductK( int [,]mat, int k) { // hash to store elements HashSet< int > s = new HashSet< int >(); // looping through elements // if present in the matrix // return true, else push // the element in matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { if ((k % mat[i, j] == 0) && s.Contains(k / mat[i, j])) { return true ; } else { s.Add(mat[i, j]); } } } return false ; } // Driver code public static void Main() { // Input matrix int [,]mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // given product int k = 42; if (isPairWithProductK(mat, k)) { Console.WriteLine( "YES" ); } else Console.WriteLine( "NO" ); } } // This code has been contributed // by PrinciRaj1992 |
Javascript
<script> // Javascript code to check for pair with given product // exists in the matrix or not let N = 4; let M = 4; function isPairWithProductK(mat,k) { // hash to store elements let s= new Set(); // looping through elements // if present in the matrix // return true, else push // the element in matrix for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if ((k % mat[i][j] == 0) && s.has(Math.floor(k / mat[i][j]))) { return true ; } else { s.add(mat[i][j]); } } } return false ; } // Driver code // Input matrix let mat = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8] , [ 9, 10, 11, 12] , [13, 14, 15, 16]] ; // given product let k = 42; if (isPairWithProductK(mat, k)) { document.write( "YES" ); } else document.write( "NO" ); // This code is contributed by rag2127 </script> |
Output
YES
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Contact Us