logo

TechCodeview

Controlla la coppia con il prodotto dato

Provalo sulla pratica GFG ' title=

Dato un array arr [] Di N numeri interi distinti e a bersaglio Valutare l'attività è verificare se ci sono una coppia di elementi nell'array il cui prodotto è uguale al target.

progettazione singleton

Esempi:  



Ingresso: arr [] = [1 5 7 -1 5] target = 35
Produzione: VERO
Spiegazione: Come 5* 7 = 35 la risposta è vera.

Ingresso: arr [] = [-10 20 9 -40] target = 30
Produzione: falso
Spiegazione: Non esiste una coppia con il prodotto 30

Tabella del contenuto



[Approccio ingenuo] generando tutte le possibili coppie - o (n 2 ) tempo e O (1) spazio

L'approccio molto semplice è generare tutte le possibili coppie e verificare se esiste una coppia il cui prodotto è uguale al valore target, quindi restituire VERO . Se non esiste tale coppia, ritorna falso .

ordinamento del secchio
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));

Produzione 
1

Complessità temporale: O (n²) per l'uso di due loop nidificati
Spazio ausiliario: O (1)

[Approccio migliore] Utilizzo della tecnica di due puntarie - O (n log (n)) tempo e O (1) spazio

Possiamo utilizzare anche la tecnica a due punterie per questo problema, ma è applicabile solo ai dati ordinati. Quindi prima ordina l'array e mantieni due puntatori un puntatore all'inizio ( Sinistra ) e un altro alla fine ( Giusto ) dell'array. Quindi controlla il prodotto degli elementi in questi due puntatori:



  • Se il prodotto è uguale al bersaglio Abbiamo trovato la coppia.
  • Se il prodotto è inferiore al bersaglio spostare il Sinistra puntatore al Giusto per aumentare il prodotto.
  • Se il prodotto è maggiore del bersaglio spostare il Giusto puntatore al Sinistra Per ridurre il prodotto.
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));

Produzione 
1

Complessità temporale: O (n log (n)) per ordinare l'array
Spazio ausiliario: O (1)

vuoto 0

[Approccio atteso] Utilizzo di hashset - o (n) tempo e O (n)

Possiamo usare un hash set per cercare in modo efficiente. Mentre ripetiamo attraverso l'array, controlliamo se ogni numero è un fattore del bersaglio. Se lo è, allora vediamo se il suo fattore corrispondente è già nel set. In tal caso torniamo VERO ; Altrimenti aggiungiamo il numero corrente al set e continuiamo.

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));

Produzione 
1

Complessità temporale: O (n) per singola iterazione
Spazio ausiliario: O (n) per la memorizzazione di elementi nel set di hash