Tutorialspoint.dev

Pair with given product | Set 1 (Find if any pair exists)

Given an array of distinct elements and a number x, find if there is a pair with a product equal to x.

Examples :

Input : arr[] = {10, 20, 9, 40};
        int x = 400;
Output : Yes

Input : arr[] = {10, 20, 9, 40};
        int x = 190;
Output : No

Input : arr[] = {-10, 20, 9, -40};
        int x = 400;
Output : Yes

Input : arr[] = {-10, 20, 9, 40};
        int x = -400;
Output : Yes

Input : arr[] = {0, 20, 9, 40};
        int x = 0;
Output : Yes


Naive approach ( O(n2) ) is to run two loops to consider all possible pairs. For every pair, check if product is equal to x or not.

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
?>


Output :

Yes
No

 



Better Solution (O(n Log n) : We sort the given array. After sorting, we traverse the array and for every element arr[i], we do binary search for x/arr[i] in the subarry on right of arr[i], i.e., in subarray arr[i+1..n-1]

 

Efficient Solution ( O(n) ): We can improve time complexity to O(n) using hashing. Below are steps.

  1. Create an empty hash table
  2. Traverse array elments and do following for every element arr[i].
    • If arr[i] is 0 and x is also 0, return true, else ignore arr[i].
    • If x % arr[i] is 0 and x/arr[i] exists in table, return true.
    • Insert arr[i] into the hash table.
  3. Return false

Below is the implementation of above idea.

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


Output :

Yes
No

In the next set, we will be discussing approach to print all pairs with product equal to 0.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter