Count number of triplets with product equal to given number

Difficulty Level Medium
Frequently asked in Accolite Amazon Cisco Flipkart Kuliza Publicis Sapient
Array Hash Two PointerViews 2313

The problem “Count number of triplets with product equal to given number” states that we are given an integer array and a number m. The problem statement asks to find out the total number of triplets of with product equals to m.

Example

arr[] = {1,5,2,6,10,3}
m=30
3

Explanation

Triplets which formed product equal to m are (1,5,6), (5,2,3) and (1,3,10)

Count number of triplets with product equal to given number

arr[] = {2,4,5,1,10}
m=20
2

Explanation

Triplets which formed product equal to m are (2,1,10), (4,5,1)

Algorithm

  1. Declare a map.
  2. Store the index of each element into the map by traversing the array.
  3. Set output to 0.
  4. Traversing the array again using a nested loop:
    1. Check if((arr[i] * arr[j] <= m) && ( arr[i] *  arr[j]  ! =  0) &&(  m % (arr[i] * arr[j]) == 0)).
      1. If this is found to be true, then find out m / (arr[i] * arr[j]) and search it in the map.
    2. Also check for, the third element we found is not equal to the current two elements (arr [i] and arr [j]).
      1. If the condition satisfies, then increase the count of output by 1.
  5. Return output.

Explanation

Our task is to find out the triplets whose product should be equal to the given number m. We are not going to use a naive approach to solve this question, it costs us more time. Rather than visiting picking each element of the triplet, we will use Hashing.

We will traverse the given array and store the index of each array element into the map along with the given array element. This is being done because later, we are going to check if the element we found should not be repeated. If the element has the same index. This means that we do not count the same array element twice for the triplet.

After the traversal of the array, we have the values in the hashmap. Set the value of output to 0. Now, we are going to use a nested loop. In which we take an element in the outer loop and in the inner loop next pick another element. Then we are going to find out the third element. All of the condition that lies in ‘if statement’ is used to find out the third element. After doing arr[i] * arr[j] all we have to find is the third element. So on a simple note, if a*b*c=m ⇒ then c = m / a * b.

Then check for the third element, if it presents in the map, means we have found it. We just have to check if the element we found should not be equal to the current two elements of the triplet. Also, current index should not have been repeated before. If all of the conditions are satisfied then we just increase the count of output by 1. This means we have one or more triplets. Then at last simply return the output.

C++ code to count number of triplets with product equal to given number

#include<iostream>
#include<unordered_map>
using namespace std;

int getProductTriplets(int arr[], int n, int m)
{
    unordered_map<int, int> numindex;
    for (int i = 0; i < n; i++)
        numindex[arr[i]] = i;

    int output = 0;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
            {
                int third = m / (arr[i] * arr[j]);
                auto it = numindex.find(third);

                if (third != arr[i] && third != arr[j]&& it != numindex.end() && it->second > i&& it->second > j)
                    output++;
            }
        }
    }
    return output;
}
int main()
{
    int arr[] = {1,5,2,6,10,3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 30;

    cout <<"Total product triplets are: "<<getProductTriplets(arr, n, m);
    return 0;
}

Total product triplets are: 3

Java code to count number of triplets with product equal to given number

import java.util.HashMap;

class TripletProductPair
{
    public static int getProductTriplets(int arr[], int n, int m)
    {
        HashMap<Integer, Integer> numindex = new HashMap<Integer, Integer>(n);
        for (int i = 0; i < n; i++)
            numindex.put(arr[i], i);

        int output = 0;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {

                if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
                {
                    int third = m / (arr[i] * arr[j]);

                    numindex.containsKey(third);
                    if (third != arr[i] && third != arr[j]&& numindex.containsKey(third) && numindex.get(third) > i && numindex.get(third) > j)
                    {
                        output++;
                    }
                }
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,5,2,6,10,3};
        int m = 30;
        System.out.println("Total product triplets are: "+getProductTriplets(arr, arr.length, m));
    }
}

Total product triplets are: 3

Complexity Analysis

Time Complexity

O(n2) where “n” is the number of elements in the array. Since we have used two nested loops and used Hashmap to search for the third element. So, this searching operation is being done by HashMap in O(1) which was previously being done in O(N) time in a naive approach. Thus this speed up is because of the HashMap.

Space Complexity

O(n) where “n” is the number of elements in the array. Because we will store all elements in the map. The space complexity is linear.

Translate »