Ein Array gegeben arr [] von N unterschiedliche Ganzzahlen und a Ziel Wert Die Aufgabe besteht darin, zu überprüfen, ob es in dem Array ein Elementpaar befindet, dessen Produkt gleich dem Ziel ist.
Kern Java
Beispiele:
Eingang: arr [] = [1 5 7 -1 5] Ziel = 35
Ausgabe: WAHR
Erläuterung: Als 5* 7 = 35 die Antwort ist wahr.Eingang: arr [] = [-10 20 9 -40] Ziel = 30
Ausgabe: FALSCH
Erläuterung: Kein Paar existiert mit Produkt 30
Inhaltstabelle
- [Naiver Ansatz] Durch Erzeugen aller möglichen Paare - o (n^2) Zeit und o (1) Raum
- [Besserer Ansatz] Mit zwei Zeigertechniken - o (n log (n)) und o (1) Raum
- [Erwarteter Ansatz] Verwenden von Hashset - O (n) Zeit und o (n) Raum
[Naiver Ansatz] durch Erzeugen aller möglichen Paare - o (n) 2 ) Zeit und o (1) Raum
C++Der sehr grundlegende Ansatz besteht darin, alle möglichen Paare zu generieren und zu überprüfen, ob ein Paar existiert, dessen Produkt dem angegebenen Zielwert entspricht, dann zurücksenden WAHR . Wenn kein solches Paar existiert, kehren Sie zurück FALSCH .
Eimersortierung
#include
#include
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)); } }
# 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))
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)); } }
// 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));
Ausgabe
1
Zeitkomplexität: O (n²) für die Verwendung von zwei verschachtelten Schleifen
Hilfsraum: O (1)
[Besserer Ansatz] Mit zwei Zeigertechniken - o (n log (n)) und o (1) Raum
C++Wir können auch die Zwei-Zeiger-Technik für dieses Problem verwenden, aber es gilt nur für sortierte Daten. Sortieren Sie also zuerst das Array und halten Sie zu Beginn zwei Zeiger ein Zeiger ( links ) und ein anderer am Ende ( Rechts ) des Arrays. Überprüfen Sie dann das Produkt der Elemente an diesen beiden Zeigern:
Konvertieren Sie char in einen String
- Wenn das Produkt dem entspricht dem Ziel Wir haben das Paar gefunden.
- Wenn das Produkt geringer ist als das Ziel bewege die links Zeiger auf die Rechts das Produkt erhöhen.
- Wenn das Produkt größer ist als das Ziel bewege die Rechts Zeiger auf die links Um das Produkt zu verringern.
#include
#include
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)); } }
# 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))
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)); } }
// 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));
Ausgabe
1
Zeitkomplexität: O (n log (n)) zum Sortieren des Arrays
Hilfsraum: O (1)
[Erwarteter Ansatz] Verwenden von Hashset - O (n) Zeit und o (n) Raum
C++Wir können a verwenden Hash -Set zum effizienten Blick nachschlagen. Während wir durch das Array iterieren, überprüfen wir, ob jede Zahl ein Faktor des Ziels ist. Wenn dies der Fall ist, sehen wir, ob sein entsprechender Faktor bereits im Satz liegt. Wenn ja, kehren wir zurück WAHR ; Andernfalls fügen wir die aktuelle Nummer zum Set hinzu und fahren fort.
#include
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)); } }
# 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))
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)); } }
// 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));
Ausgabe
1
Zeitkomplexität: O (n) für eine Iteration
Hilfsraum: O (n) für die Aufbewahrung von Elementen im Hash -Set