给定一个不同元素的数组和一个数字x，找出是否有一对乘积等于x。
null
例如：
Input : arr[] = {10, 20, 9, 40}; int x = 400;Output : YesInput : arr[] = {10, 20, 9, 40}; int x = 190;Output : NoInput : arr[] = {-10, 20, 9, -40}; int x = 400;Output : YesInput : arr[] = {-10, 20, 9, 40}; int x = -400;Output : YesInput : arr[] = {0, 20, 9, 40}; int x = 0;Output : Yes
这个 天真的方法（O（n） 2. ) ) 是运行两个循环来考虑所有可能的对。对于每一对，检查乘积是否等于x。
C++
// A simple C++ program to find if there is a pair // with given product. #include<bits/stdc++.h> using namespace std; // Returns true if there is a pair in arr[0..n-1] // with product equal to x. bool isProduct( int arr[], int n, int x) { // Consider all possible pairs and check for // every pair. for ( int i=0; i<n-1; i++) for ( int j=i+1; i<n; i++) if (arr[i] * arr[j] == x) return true ; return false ; } // Driver code int main() { int arr[] = {10, 20, 9, 40}; int x = 400; int n = sizeof (arr)/ sizeof (arr[0]); isProduct(arr, n, x)? cout << "Yesn" : cout << "Non" ; x = 190; isProduct(arr, n, x)? cout << "Yesn" : cout << "Non" ; return 0; } |
JAVA
// Java program to find if there is a pair // with given product. class GFG { // Returns true if there is a pair in // arr[0..n-1] with product equal to x. boolean isProduct( int arr[], int n, int x) { for ( int i= 0 ; i<n- 1 ; i++) for ( int j=i+ 1 ; j<n; j++) if (arr[i]*arr[j] == x) return true ; return false ; } // Driver code public static void main(String[] args) { GFG g = new GFG(); int arr[] = { 10 , 20 , 9 , 40 }; int x = 400 ; int n = arr.length; if (g.isProduct(arr, n, x)) System.out.println( "Yes" ); else System.out.println( "No" ); x = 190 ; if (g.isProduct(arr, n, x)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Kamal Rawal |
Python3
# Python3 program to find if there # is a pair with given product. # Returns true if there is a # pair in arr[0..n-1] with # product equal to x def isProduct(arr, n, x): for i in arr: for j in arr: if i * j = = x: return True return False # Driver code arr = [ 10 , 20 , 9 , 40 ] x = 400 n = len (arr) if (isProduct(arr,n, x) = = True ): print ( "Yes" ) else : print ( "No" ) x = 900 if (isProduct(arr, n, x)): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by prerna saini |
C#
// C# program to find // if there is a pair // with given product. using System; class GFG { // Returns true if there // is a pair in arr[0..n-1] // with product equal to x. static bool isProduct( int []arr, int n, int x) { for ( int i = 0; i < n - 1; i++) for ( int j = i + 1; j < n; j++) if (arr[i] * arr[j] == x) return true ; return false ; } // Driver Code static void Main() { int []arr = {10, 20, 9, 40}; int x = 400; int n = arr.Length; if (isProduct(arr, n, x)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); x = 190; if (isProduct(arr, n, x)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed // by Sam007 |
PHP
<?php // A simple php program to // find if there is a pair // with given product. // Returns true if there // is a pair in arr[0..n-1] // with product equal to x. function isProduct( $arr , $n , $x ) { // Consider all possible // pairs and check for // every pair. for ( $i = 0; $i < $n - 1; $i ++) for ( $j = $i + 1; $i < $n ; $i ++) if ( $arr [ $i ] * $arr [ $j ] == $x ) return true; return false; } // Driver code $arr = array (10, 20, 9, 40); $x = 400; $n = count ( $arr ); if (isProduct( $arr , $n , $x )) echo "Yes" ; else echo "No" ; $x = 190; if (isProduct( $arr , $n , $x )) echo "Yes" ; else echo "No" ; // This code is contributed // by Sam007 ?> |
Javascript
<script> // A simple Javascript program to find if there is a pair // with given product. // Returns true if there is a pair in arr[0..n-1] // with product equal to x. function isProduct(arr, n, x) { // Consider all possible pairs and check for // every pair. for ( var i=0; i<n-1; i++) for ( var j=i+1; i<n; i++) if (arr[i] * arr[j] == x) return true ; return false ; } // Driver code var arr = [10, 20, 9, 40]; var x = 400; var n = arr.length; isProduct(arr, n, x)? document.write( "Yes<br>" ) : document.write( "No<br>" ); x = 190; isProduct(arr, n, x)? document.write( "Yes" ) : document.write( "No" ); </script> |
输出：
YesNo
更好的解决方案（O（n日志n）： 我们对给定的数组进行排序。排序后，我们遍历数组，对于每个元素arr[i]，我们在arr[i]右侧的子数组中对x/arr[i]进行二进制搜索，即子数组arr[i+1..n-1]
有效解（O（n））： 我们可以使用 散列 .以下是步骤。
- 创建一个空哈希表
- 遍历数组元素，并对每个元素arr[i]执行以下操作。
- 如果arr[i]为0，x也为0，则返回true，否则忽略arr[i]。
- 如果x%arr[i]为0且表中存在x/arr[i]，则返回true。
- 将arr[i]插入哈希表。
- 返回false
下面是上述想法的实施。
C++
// C++ program to find if there is a pair // with given product. #include<bits/stdc++.h> using namespace std; // Returns true if there is a pair in arr[0..n-1] // with product equal to x. bool isProduct( int arr[], int n, int x) { if (n < 2) return false ; // Create an empty set and insert first // element into it unordered_set< int > s; // Traverse remaining elements for ( int i=0; i<n; i++) { // 0 case must be handles explicitly as // x % 0 is undefined behaviour in C++ if (arr[i] == 0) { if (x == 0) return true ; else continue ; } // x/arr[i] exists in hash, then we // found a pair if (x%arr[i] == 0) { if (s.find(x/arr[i]) != s.end()) return true ; // Insert arr[i] s.insert(arr[i]); } } return false ; } // Driver code int main() { int arr[] = {10, 20, 9, 40}; int x = 400; int n = sizeof (arr)/ sizeof (arr[0]); isProduct(arr, n, x)? cout << "Yes" : cout << "Non" ; x = 190; isProduct(arr, n, x)? cout << "Yes" : cout << "Non" ; return 0; } |
JAVA
// Java program if there exists a pair for given product import java.util.HashSet; class GFG { // Returns true if there is a pair in arr[0..n-1] // with product equal to x. static boolean isProduct( int arr[], int n, int x) { // Create an empty set and insert first // element into it HashSet<Integer> hset = new HashSet<>(); if (n < 2 ) return false ; // Traverse remaining elements for ( int i = 0 ; i < n; i++) { // 0 case must be handles explicitly as // x % 0 is undefined if (arr[i] == 0 ) { if (x == 0 ) return true ; else continue ; } // x/arr[i] exists in hash, then we // found a pair if (x % arr[i] == 0 ) { if (hset.contains(x / arr[i])) return true ; // Insert arr[i] hset.add(arr[i]); } } return false ; } // driver code public static void main(String[] args) { int arr[] = { 10 , 20 , 9 , 40 }; int x = 400 ; int n = arr.length; if (isProduct(arr, arr.length, x)) System.out.println( "Yes" ); else System.out.println( "No" ); x = 190 ; if (isProduct(arr, arr.length, x)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Kamal Rawal |
Python3
# Python3 program to find if there # is a pair with the given product. # Returns true if there is a pair in # arr[0..n-1] with product equal to x. def isProduct(arr, n, x): if n < 2 : return False # Create an empty set and insert # first element into it s = set () # Traverse remaining elements for i in range ( 0 , n): # 0 case must be handles explicitly as # x % 0 is undefined behaviour in C++ if arr[i] = = 0 : if x = = 0 : return True else : continue # x/arr[i] exists in hash, then # we found a pair if x % arr[i] = = 0 : if x / / arr[i] in s: return True # Insert arr[i] s.add(arr[i]) return False # Driver code if __name__ = = "__main__" : arr = [ 10 , 20 , 9 , 40 ] x = 400 n = len (arr) if isProduct(arr, n, x): print ( "Yes" ) else : print ( "No" ) x = 190 if isProduct(arr, n, x): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Rituraj Jain |
C#
// C# program if there exists a // pair for given product using System; using System.Collections.Generic; class GFG { // Returns true if there is a pair // in arr[0..n-1] with product equal to x. public static bool isProduct( int [] arr, int n, int x) { // Create an empty set and insert // first element into it HashSet< int > hset = new HashSet< int >(); if (n < 2) { return false ; } // Traverse remaining elements for ( int i = 0; i < n; i++) { // 0 case must be handles explicitly // as x % 0 is undefined if (arr[i] == 0) { if (x == 0) { return true ; } else { continue ; } } // x/arr[i] exists in hash, then // we found a pair if (x % arr[i] == 0) { if (hset.Contains(x / arr[i])) { return true ; } // Insert arr[i] hset.Add(arr[i]); } } return false ; } // Driver Code public static void Main( string [] args) { int [] arr = new int [] {10, 20, 9, 40}; int x = 400; int n = arr.Length; if (isProduct(arr, arr.Length, x)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } x = 190; if (isProduct(arr, arr.Length, x)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program if there exists a pair for given product // Returns true if there is a pair in arr[0..n-1] // with product equal to x. function isProduct(arr, n, x) { // Create an empty set and insert first // element into it let hset = new Set(); if (n < 2) return false ; // Traverse remaining elements for (let i = 0; i < n; i++) { // 0 case must be handles explicitly as // x % 0 is undefined if (arr[i] == 0) { if (x == 0) return true ; else continue ; } // x/arr[i] exists in hash, then we // found a pair if (x % arr[i] == 0) { if (hset.has(x / arr[i])) return true ; // Insert arr[i] hset.add(arr[i]); } } return false ; } // Driver program let arr = [10, 20, 9, 40]; let x = 400; let n = arr.length; if (isProduct(arr, arr.length, x)) document.write( "Yes" + "<br/>" ); else document.write( "No" + "<br/>" ); x = 190; if (isProduct(arr, arr.length, x)) document.write( "Yes" + "<br/>" ); else document.write( "No" + "<br/>" ); </script> |
输出：
YesNo
在下一集中，我们将讨论打印乘积等于0的所有对的方法。 本文由 Shubham Goyal 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
