Controlla la coppia con il prodotto dato
Provalo sulla pratica GFG 
Produzione
Produzione
Produzione
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.
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
- [Approccio migliore] Utilizzo della tecnica di due puntarie - O (n log (n)) tempo e O (1) spazio
- [Approccio atteso] Utilizzo di hashset - o (n) tempo e O (n)
[Approccio ingenuo] generando tutte le possibili coppie - o (n 2 ) tempo e O (1) spazio
C++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 .
#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 ( 1L L * 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 ( 1L L * 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 ( '%d n ' 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
C++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.
#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 = 1L L * 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 ( '%d n ' 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)
[Approccio atteso] Utilizzo di hashset - o (n) tempo e O (n)
C++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.
#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
