Count Ways to Form Minimum Product Triplets in C++

We are given with an array of numbers Arr[]. The goal is count the number of triplets whose product is equal to the smallest product of all possible triplets.Count triplets if (i<j<k) and arr[i]*arr[j]*arr[k] is minimum possible.

We will do this by first finding the smallest product where (i<j<k). And store as minprod. Then count all those triplets that have product=minprod.

Let’s understand with examples.

Input − arr[]= { 1,2,3,2,4,1,5 }

Output − Number of triplets − 2

Explanation −

Here minimum product is 2
Triplet 1[ 1,2,3,2,4,1,5 ] → (1,2,1) product=2
Triplet 2 [ 1,2,3,2,4,1,5 ] → (1,2,1) product=2
Number of triplets with product 2 which is minimum is 2.

Input − arr[]= { 1,1,2,1,2,2 }

Output − Number of triplets − 1

Explanation −

Here minimum product is 1
Triplet 1 [ 1,1,2,1,2,2 ] → (1,1,1) product=1
Number of triplets with product 1 which is minimum is 1.

Approach used in the below program is as follows

• We take an integer array Arr[] initialized with random numbers.

• Take a variable N which stores the length of Arr[].

• Function countTriplets(int arr[], int n) takes an array, its length as input and returns the triplets whose product is equal to the minimum product.

• Take the initial variable count as 0 for the number of triplets.

• Take the initial variable prod as the product of each triplet. Initially 1.

• Take the initial variable minprod as the minimum possible product of all triplets. Initially 999.

• Traverse array using three for loops for each element of the triplet.

• Outermost loop from 0<=i<n-2, inner loop i<j<n-1, innermost j<k<n.

• Calculate prod=arr[i]*arr[j]*arr[k]. If prod<=minprod then update minprod with prod.

• Now minprod has the value of least product of all triplets.

• Again traverse array using three for loops for each element of the triplet.

• Outermost loop from 0<=i<n-2, inner loop i<j<n-1, innermost j<k<n.

• Calculate prod=arr[i]*arr[j]*arr[k]. If prod==minprod then increment count. As this pair has the minimum product.

• At the end of all loops count will have a total number of triplets that meet the condition.

• Return the count as result.

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[],int n){
   int count = 0;
   int prod=1;
   int minprod=9999; //making minimum as larger than any product in array
   for (int i = 0; i < n-2; i++){
      for (int j = i+1; j < n-1; j++){
         for (int k = j+1; k < n; k++){
            prod=arr[i]*arr[j]*arr[k];
            if ( prod<=minprod )
               { minprod=prod; }
         }
      }
   }
   // cout<<"minproduct :"<<minprod; //to print minimum product
   for (int i = 0; i < n-2; i++){
      for (int j = i+1; j < n-1; j++){
         for (int k = j+1; k < n; k++){
            prod=arr[i]*arr[j]*arr[k];
            if ( prod==minprod ){
               count++;
               //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]<<" c :"<<arr[k]; //to print
            }
         }
      }
   }
   return count;
}
int main(){
   int Arr[]={ 1,2,3,1,2,6};
   int N=5; //length of array
   cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N);
   return 0;
}

Output

If we run the above code it will generate the following output −

Number of triplets : 2