Dada una array NxM y un producto K. La tarea es verificar si existe un par con el producto dado en la array o no.
Ejemplos :
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
Acercarse:
- Tome un hash para almacenar todos los elementos de la array en el hash.
- Comience a atravesar la array y, mientras la atraviesa, verifique si el elemento actual de la array es divisible por el producto dado y cuando el producto K se divide por el elemento actual, el dividendo obtenido también está presente en el hash.
Eso es,
(k % mat[i][j] == 0) && (mp[k / mat[i][j]] > 0)
- Si está presente, devuelve verdadero; de lo contrario, inserte los elementos actuales en el hash.
- Si se recorren todos los elementos de la array y no se encuentra ningún par, devuelve falso.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
YES
Complejidad de tiempo : O(N*M)