Sjekk paret med gitt produkt
Prøv det på GFG -praksis 
Produksjon
Produksjon
Produksjon
Gitt en matrise arr [] av n distinkte heltall og en mål Verdi oppgaven er å sjekke om det er et par elementer i matrisen hvis produkt er lik målet.
Eksempler:
: arr [] = [1 5 7 -1 5] Mål = 35
Produksjon: ekte
Forklaring: Som 5* 7 = 35 er svaret sant.: arr [] = [-10 20 9 -40] mål = 30
Produksjon: falsk
Forklaring: Ingen par eksisterer med produkt 30
Tabell over innhold
- [Naiv tilnærming] Ved å generere alle mulige par - O (N^2) Tid og O (1) plass
- [Bedre tilnærming] Bruke to pekerteknikk - O (n log (n)) tid og O (1) plass
- [Forventet tilnærming] Bruke hashset - o (n) tid og o (n) plass
[Naiv tilnærming] ved å generere alle mulige par - o (n 2 ) tid og o (1) plass
C++Den helt grunnleggende tilnærmingen er å generere alle mulige par og sjekke om noe par eksisterer hvis produkt er likeverdige til gitt målverdi og deretter returnere ekte . Hvis det ikke eksisterer noe slikt, så returner falsk .
#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 ));
Produksjon
1
Tidskompleksitet: O (n²) for bruk av to nestede løkker
Hjelpeplass: O (1)
[Bedre tilnærming] Bruke to pekerteknikk - O (n log (n)) tid og O (1) plass
C++Vi kan bruke to-pekerteknikken for dette problemet også, men det er bare aktuelt for sorterte data. Så sorter først matrisen og hold to pekere en peker i begynnelsen ( Igjen ) og en annen på slutten ( høyre ) av matrisen. Sjekk deretter produktet av elementene på disse to pekerne:
- Hvis produktet tilsvarer mål Vi har funnet paret.
- Hvis produktet er mindre enn mål Flytt Igjen peker til høyre for å øke produktet.
- Hvis produktet er større enn mål Flytt høyre peker til Igjen for å redusere produktet.
#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 ));
Produksjon
1
Tidskompleksitet: O (n log (n)) for å sortere matrisen
Hjelpeplass: O (1)
[Forventet tilnærming] Bruke hashset - o (n) tid og o (n) plass
C++Vi kan bruke en Hash sett for effektivt å slå opp. Når vi itererer gjennom matrisen, sjekker vi om hvert nummer er en faktor for målet. Hvis det er det, ser vi om den tilsvarende faktoren allerede er i settet. I så fall kommer vi tilbake ekte ; Ellers legger vi gjeldende nummer til settet og fortsetter.
#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 ));
Produksjon
1
Tidskompleksitet: O (n) for enkelt iterasjon
Hjelpeplass: O (n) for lagring av elementer i hasjsettet
