Pair with given product

Difficulty Level Medium
Frequently asked in 24*7 Innovation Labs Amazon Avalara Quora Roblox
Array Hash MathViews 2749

The problem “Pair with given product” states that you are given an integer array and a number “x”. Determine, whether an array consists of a pair of which product equals ‘x’ exist in the given input array.

Example

[2,30,12,5]
x = 10
Yes, it has Product Pair

Explanation

Pair with given product

Here 2 and 5 are the elements whose product is equal to 10 i.e., x.

[10,30,12,50]
x = 40
No, it does not have a Product Pair.

Explanation

There is no such pair in the array whose product is equal to x i.e., 40.

[20,3,12,5]
x = 100
Yes, it has a Product Pair.

Explanation

Here 20 and 5 in the array forms a pair whose product equals to x i.e., 100.

Algorithm to find if Pair with given product exists

  1. Declare a HashSet.
  2. Check the length of the array if at least 2 values are given.
    1. If not, return false.
  3. While i < n.
    1. Check if one of the elements of the array is equal to 0
      1. If x is also given 0, then return true.
    2. Check if x can be divided by any of the elements of arr and gives remainder 0.
      1. If HashSet contains (x/arr[i]), then return true.
      2. Add the arr[i] to HashSet.
  4. Return false.

Explanation

We are given a problem in which an array and a number is given. Then we have to find out if any pair exists in the input array which has a Product equal to x. We are going to use hashing to solve this problem. To find out the value which exists in an array with a given Product. We divide the x with arr[i] and check if the remainder is 0. If found to be 0 then we will check if x/arr[i] exist in the HashSet. If it exists then we will return true. If not, just add that element array into HashSet for further traversal.

We are also given a condition which is to explicitly check the zero Product. If our x value is given as 0 we will check if any of the elements of the array is 0. And if it is, then we return true because zero multiplied by anything is always zero.

Let us take an example and understand this:

arr[]={10,20,9,40}, X=90

i=0, arr[i]=10,

We will check for if arr[i] is equal to 0 but in this array not even a single element is 0, so it will not execute in any iteration.

We will here just check it if x%arr[i] = = 0 if it passes then we will check if x/arr[i] is in set or not.

90%10==0 is true and 90/10=9 is not in a HashSet yet.

So we will add arr[i] =10 into set.

90%20==0 is false, and nothing happens

90%9==0 is true and 90/9=10 is present in a HashSet as we already inserted in a HashSet.

So it means we do have a Product pair as 9 and 10 in an array and returns true and prints

Output: “Yes, it has Product Pair”.

C++ code to find pair with given productAmazon

#include<iostream>
#include<unordered_set>
using namespace std;
bool getProduct (int arr[], int n, int x)
{
  if (n < 2)
    return false;

  unordered_set<int> s;

  for (int i=0; i<n; i++)
  {
    if (arr[i] == 0)
    {
    if (x == 0)
      return true;
    else
      continue;
    }
    if (x%arr[i] == 0)
    {
      if (s.find(x/arr[i]) != s.end())
                return true;

      s.insert(arr[i]);
    }
  }
  return false;
}
int main()
{
  int arr[] = {10, 20, 9, 40};
  int x = 90;
  int n = sizeof(arr)/sizeof(arr[0]);
  getProduct (arr, n, x)? cout << "Yes, it has Product Pair\n":cout << "No, it does not have Product Pair";
  return 0;
}

Yes, it has Product Pair

Java code to find Pair with given product

import java.util.HashSet;

class pairX
{
    public static boolean getProduct (int arr[], int n, int x)
    {
        HashSet<Integer> mySet = new HashSet<>();

        if(n < 2)
            return false;

        for(int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
            {
                if(x == 0)
                    return true;
                else
                    continue;
            }
            if(x % arr[i] == 0)
            {
                if(mySet.contains(x / arr[i]))
                    return true;

                mySet.add(arr[i]);
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = {10, 20, 9, 40};
        int x = 90;
        int n = arr.length;

        if(getProduct (arr, n, x))
            System.out.println("Yes, it has Product Pair");
        else
            System.out.println("No, it does not have Product Pair");
    }
}

Yes, it has Product Pair

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Since we have used HashSet, we were able to perform insert, delete and search in O(1) time. Because of which we were able to achieve linear time complexity.

Space Complexity

O(n) where “n” is the number of elements in the array. If all the elements will be stored in the HashSet, then it will have N terms. That will cost us linear space. Because as the input increases the space increases.

Translate »