logo

TechCodeview

Verifique el par con el producto dado

Pruébalo en la práctica GFG ' title=

Dada una matriz arr [] de norte enteros distintos y un objetivo Valor La tarea es verificar si hay un par de elementos en la matriz cuyo producto es igual al objetivo.

java tiene el siguiente

Ejemplos:  



Aporte: arr [] = [1 5 7 -1 5] objetivo = 35
Producción: verdadero
Explicación: Como 5* 7 = 35 La respuesta es verdadera.

Aporte: arr [] = [-10 20 9 -40] objetivo = 30
Producción: FALSO
Explicación: No existe un par con el producto 30

Tabla de contenido



[Enfoque ingenuo] generando todos los pares posibles - o (n 2 ) Tiempo y o (1) espacio

El enfoque muy básico es generar todos los pares posibles y verificar si existe algún par cuyo producto es igual a un valor objetivo dado y luego regresar y luego devolver verdadero . Si no existe tal par, entonces regresa FALSO .

cucharadita vs cucharada
C++ 
#include    using namespace std; // Function to check if any pair exists whose product // equals the target bool isProduct(vector<int> &arr long long target) {  int n = arr.size();  for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++) {  if (1LL * arr[i] * arr[j] == target) {  return true;  }  }  }  return false; } int main() {  vector<int> arr = {1 5 7 -1 5};  long long target = 35;  cout << isProduct(arr target) << endl;  return 0; }
C 
#include  #include  // Function to check if any pair exists whose product // equals the target bool isProduct(int arr[] int n long long target) {  for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++) {  if (1LL * arr[i] * arr[j] == target) {  return true;  }  }  }  return false; } int main() {  int arr[] = {1 5 7 -1 5};  long long target = 35;   int n = sizeof(arr) / sizeof(arr[0]);  printf('%dn' isProduct(arr n target));    return 0; }
Java 
class GfG {  // Function to check if any pair exists whose product  // equals the target  static boolean isProduct(int[] arr long target) {  int n = arr.length;  for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++) {  if ((long) arr[i] * arr[j] == target) {  return true;  }  }  }  return false;  }  public static void main(String[] args) {  int[] arr = {1 5 7 -1 5};  long target = 35;   System.out.println(isProduct(arr target));  } }
Python 
# Function to check if any pair exists whose product # equals the target def is_product(arr target): n = len(arr) for i in range(n - 1): for j in range(i + 1 n): if arr[i] * arr[j] == target: return True return False arr = [1 5 7 -1 5] target = 35 print(is_product(arr target))
C# 
using System; class GfG {  // Function to check if any pair exists whose product  // equals the target  static bool IsProduct(int[] arr long target) {  int n = arr.Length;  for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++) {  if ((long)arr[i] * arr[j] == target) {  return true;  }  }  }  return false;  }  static void Main() {  int[] arr = { 1 5 7 -1 5 };  long target = 35;   Console.WriteLine(IsProduct(arr target));  } }
JavaScript 
// Function to check if any pair exists whose product // equals the target function isProduct(arr target) {  let n = arr.length;  for (let i = 0; i < n - 1; i++) {  for (let j = i + 1; j < n; j++) {  if (arr[i] * arr[j] === target) {  return true;  }  }  }  return false; } let arr = [1 5 7 -1 5]; let target = 35; console.log(isProduct(arr target));

Producción 
1

Complejidad del tiempo: O (n²) para usar dos bucles anidados
Espacio auxiliar: O (1)

[Mejor enfoque] Utilizando la técnica de dos puntos - o (n log (n)) tiempo y espacio o (1)

También podemos usar la técnica de dos puntos para este problema, pero solo es aplicable a los datos ordenados. Así que primero ordene la matriz y mantenga dos punteros un puntero al principio ( izquierda ) y otro al final ( bien ) de la matriz. Luego verifique el producto de los elementos en estos dos punteros:



  • Si el producto es igual al objetivo Hemos encontrado el par.
  • Si el producto es menor que el objetivo mover el izquierda puntero al bien para aumentar el producto.
  • Si el producto es mayor que el objetivo mover el bien puntero al izquierda para disminuir el producto.
C++ 
#include    using namespace std; // Function to check if any pair exists whose product equals the target. bool isProduct(vector<int> &arr long long target) {    // Sort the array  sort(arr.begin() arr.end());  int left = 0 right = arr.size() - 1;  while (left < right) {  // Calculate the current product  long long currProd = 1LL*arr[left]*arr[right];  // If the product matches the target return true.  if (currProd == target) return true;  // Move the pointers based on comparison with target.  if (currProd > target) right--;  else left++;  }  return false; } int main() {  vector<int> arr = {1 5 7 -1 5};  long long target = 35;  cout << isProduct(arr target) << endl;  return 0; }
C 
#include  #include  #include  // Function to compare two integers (used in qsort) int compare(const void *a const void *b) {  return (*(int *)a - *(int *)b); } // Function to check if any pair exists whose product // equals the target. bool isProduct(int arr[] int n long long target) {  // Sort the array  qsort(arr n sizeof(int) compare);  int left = 0 right = n - 1;  while (left < right)  {  // Calculate the current product  long long currProd = (long long)arr[left] * arr[right];  // If the product matches the target return true.  if (currProd == target)  return true;  // Move the pointers based on comparison with target.  if (currProd > target)  right--;  else  left++;  }  return false; } int main() {  int arr[] = {1 5 7 -1 5};  long long target = 35;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%dn' isProduct(arr n target));  return 0; }
Java 
import java.util.Arrays; class GfG {  // Function to check if any pair exists whose product equals the target.  static boolean isProduct(int[] arr long target) {  // Sort the array  Arrays.sort(arr);  int left = 0 right = arr.length - 1;  while (left < right) {    // Calculate the current product  long currProd = (long) arr[left] * arr[right];  // If the product matches the target return true.  if (currProd == target) return true;  // Move the pointers based on comparison with target.  if (currProd > target) right--;  else left++;  }  return false;  }  public static void main(String[] args) {  int[] arr = {1 5 7 -1 5};  long target = 35;   System.out.println(isProduct(arr target));  } }
Python 
# Function to check if any pair exists whose product equals the target. def isProduct(arr target): # Sort the array arr.sort() left right = 0 len(arr) - 1 while left < right: # Calculate the current product currProd = arr[left] * arr[right] # If the product matches the target return True. if currProd == target: return True # Move the pointers based on comparison with target. if currProd > target: right -= 1 else: left += 1 return False if __name__ == '__main__': arr = [1 5 7 -1 5] target = 35 print(isProduct(arr target))
C# 
using System; using System.Linq; class GfG {  // Function to check if any pair exists whose product  // equals the target.  static bool isProduct(int[] arr long target) {    // Sort the array  Array.Sort(arr);  int left = 0 right = arr.Length - 1;  while (left < right) {  // Calculate the current product  long currProd = (long) arr[left] * arr[right];  // If the product matches the target return true.  if (currProd == target) return true;  // Move the pointers based on comparison with target.  if (currProd > target) right--;  else left++;  }  return false;  }  static void Main(string[] args) {  int[] arr = { 1 5 7 -1 5 };  long target = 35;   Console.WriteLine(isProduct(arr target));  } }
JavaScript 
// Function to check if any pair exists whose product // equals the target. function isProduct(arr target) {  // Sort the array  arr.sort((a b) => a - b);  let left = 0 right = arr.length - 1;  while (left < right) {  // Calculate the current product  let currProd = arr[left] * arr[right];  // If the product matches the target return true.  if (currProd === target) return true;  // Move the pointers based on comparison with target.  if (currProd > target) right--;  else left++;  }  return false; } let arr = [1 5 7 -1 5]; let target = 35; console.log(isProduct(arr target));

Producción 
1

Complejidad del tiempo: O (n log (n)) para clasificar la matriz
Espacio auxiliar: O (1)

tiene el siguiente java

[Enfoque esperado] Uso de hashset - o (n) tiempo y o (n) espacio

Podemos usar un set de hash para buscar eficientemente. A medida que iteramos a través de la matriz, verificamos si cada número es un factor del objetivo. Si es así, vemos si su factor correspondiente ya está en el conjunto. Si es así, regresamos verdadero ; De lo contrario, agregamos el número actual al conjunto y continuamos.

C++ 
#include    #include  #include  using namespace std; // Function to check if any pair exists whose product // equals the target. bool isProduct(vector<int> &arr long long target) {    // Use an unordered set to store previously seen numbers.  unordered_set<int> st;  for (int num : arr) {  // If target is 0 and current number is 0 return true.  if (target == 0 && num == 0) return true;  // Check if current number can be a factor of the target.  if (target % num == 0) {  int secondNum = target / num;    // If the secondNum has been seen before return true.  if (st.find(secondNum) != st.end()) {  return true;  }    // Mark the current number as seen.  st.insert(num);  }  }  return false; } int main() {  vector<int> arr = {1 5 7 -1 5};  long long target = 35;  cout << isProduct(arr target) << endl;  return 0; }
Java 
import java.util.HashSet; class GfG {  // Function to check if any pair exists whose product  // equals the target.  static boolean isProduct(int[] arr long target)  {  // Use a hash set to store previously seen numbers.  HashSet<Integer> set = new HashSet<>();  for (int num : arr) {  // If target is 0 and current number is 0  // return true.  if (target == 0 && num == 0)  return true;  // Check if current number can be a factor of  // the target.  if (target % num == 0) {  int secondNum = (int)(target / num);  // If the secondNum has been seen before  // return true.  if (set.contains(secondNum))  return true;  // Mark the current number as seen.  set.add(num);  }  }  return false;  }  public static void main(String[] args)  {  int[] arr = { 1 5 7 -1 5 };  long target = 35;  System.out.println(isProduct(arr target));  } }
Python 
# Function to check if any pair exists whose product equals the target. def isProduct(arr target): # Use a set to store previously seen numbers. st = set() for num in arr: # If target is 0 and current number is 0 return True. if target == 0 and num == 0: return True # Check if current number can be a factor of the target. if target % num == 0: secondNum = target // num # If the secondNum has been seen before return True. if secondNum in st: return True # Mark the current number as seen. st.add(num) return False if __name__ == '__main__': arr = [1 5 7 -1 5] target = 35 print(isProduct(arr target))
C# 
using System; using System.Collections.Generic; class GfG {  // Function to check if any pair exists whose product  // equals the target.  static bool isProduct(int[] arr long target)  {  // Use a hash set to store previously seen numbers.  HashSet<int> set = new HashSet<int>();  foreach(int num in arr)  {  // If target is 0 and current number is 0  // return true.  if (target == 0 && num == 0)  return true;  // Check if current number can be a factor of  // the target.  if (target % num == 0) {  int secondNum = (int)(target / num);  // If the secondNum has been seen before  // return true.  if (set.Contains(secondNum))  return true;  // Mark the current number as seen.  set.Add(num);  }  }  return false;  }  static void Main(string[] args)  {  int[] arr = { 1 5 7 -1 5 };  long target = 35;  Console.WriteLine(isProduct(arr target));  } }
JavaScript 
// Function to check if any pair exists whose product equals // the target. function isProduct(arr target) {  // Use a set to store previously seen numbers.  let seen = new Set();  for (let num of arr) {  // If target is 0 and current number is 0 return  // true.  if (target === 0 && num === 0)  return true;  // Check if current number can be a factor of the  // target.  if (target % num === 0) {  let secondNum = target / num;  // If the secondNum has been seen before return  // true.  if (seen.has(secondNum))  return true;  // Mark the current number as seen.  seen.add(num);  }  }  return false; } let arr = [ 1 5 7 -1 5 ]; let target = 35; console.log(isProduct(arr target));

Producción 
1

Complejidad del tiempo: O (n) para iteración única
Espacio auxiliar: O (n) para almacenar elementos en el set hash