Count number of triplets with product equal to given number | Set 2

Namachila November 18, 2025

0 0 5 minutes read

Given an array of distinct integers(considering only positive numbers) and a number ‘m’, find the number of triplets with the product equal to ‘m’.

Examples:

Input: arr[] = { 1, 4, 6, 2, 3, 8}  
            m = 24
Output: 3

Input: arr[] = { 0, 4, 6, 2, 3, 8}  
            m = 18
Output: 0

An approach with O(n) extra space has already been discussed in previous post. In this post an approach with O(1) space complexity will be discussed.

Approach: The idea is to use Three-pointer technique:

Sort the input array.
Fix the first element as A[i] where i is from 0 to array size – 2.
After fixing the first element of triplet, find the other two elements using 2 pointer technique.

Below is the implementation of above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count such triplets
int countTriplets(int arr[], int n, int m)
{
    int count = 0;
 
    // Sort the array
    sort(arr, arr + n);
    int end, start, mid;
 
    // three pointer technique
    for (end = n - 1; end >= 2; end--) {
        int start = 0, mid = end - 1;
        while (start < mid) {
 
            // Calculate the product of a triplet
            long int prod = arr[end] * arr[start] * arr[mid];
 
            // Check if that product is greater than m,
            // decrement mid
            if (prod > m)
                mid--;
 
            // Check if that product is smaller than m,
            // increment start
            else if (prod < m)
                start++;
 
            // Check if that product is equal to m,
            // decrement mid, increment start and
            // increment the count of pairs
            else if (prod == m) {
                count++;
                mid--;
                start++;
            }
        }
    }
 
    return count;
}
 
// Drivers code
int main()
{
    int arr[] = { 1, 1, 1, 1, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 1;
 
    cout << countTriplets(arr, n, m);
 
    return 0;
}

Java

// Java implementation of 
// above approach
import java.io.*;
import java.util.*;
 
class GFG 
{
 
// Function to count such triplets
static int countTriplets(int arr[],
                         int n, int m)
{
    int count = 0;
 
    // Sort the array
    Arrays.sort(arr);
    int end, start, mid;
 
    // three pointer technique
    for (end = n - 1; end >= 2; end--) 
    {
        start = 0; mid = end - 1;
        while (start < mid)
        {
 
            // Calculate the product
            // of a triplet
            long prod = arr[end] * 
                        arr[start] * 
                        arr[mid];
 
            // Check if that product 
            // is greater than m,
            // decrement mid
            if (prod > m)
                mid--;
 
            // Check if that product 
            // is smaller than m,
            // increment start
            else if (prod < m)
                start++;
 
            // Check if that product is equal 
            // to m, decrement mid, increment
            // start and increment the 
            // count of pairs
            else if (prod == m) 
            {
                count++;
                mid--;
                start++;
            }
        }
    }
 
    return count;
}
 
// Driver code
public static void main (String[] args) 
{
    int []arr = { 1, 1, 1, 1, 1, 1 };
    int n = arr.length;
    int m = 1;
     
    System.out.println(countTriplets(arr, n, m));
}
}
 
// This code is contributed 
// by inder_verma.

Python3

# Python3 implementation 
# of above approach
 
# Function to count such triplets
def countTriplets(arr, n, m):
 
    count = 0
 
    # Sort the array
    arr.sort()
 
    # three pointer technique
    for end in range(n - 1, 1, -1) :
        start = 0
        mid = end - 1
        while (start < mid) :
 
            # Calculate the product 
            # of a triplet
            prod = (arr[end] *
                    arr[start] * arr[mid])
 
            # Check if that product is 
            # greater than m, decrement mid
            if (prod > m):
                mid -= 1
 
            # Check if that product is 
            # smaller than m, increment start
            elif (prod < m):
                start += 1
 
            # Check if that product is equal 
            # to m, decrement mid, increment 
            # start and increment the count 
            # of pairs
            elif (prod == m):
                count += 1
                mid -= 1
                start += 1
 
    return count
 
# Drivers code
if __name__ == "__main__":
    arr = [ 1, 1, 1, 1, 1, 1 ]
    n = len(arr)
    m = 1
 
    print(countTriplets(arr, n, m))
 
# This code is contributed 
# by ChitraNayal

C#

// C# implementation of above approach
using System;
 
class GFG 
{
 
// Function to count such triplets
static int countTriplets(int []arr,
                         int n, int m)
{
    int count = 0;
 
    // Sort the array
    Array.Sort(arr);
    int end, start, mid;
 
    // three pointer technique
    for (end = n - 1; end >= 2; end--) 
    {
        start = 0; mid = end - 1;
        while (start < mid)
        {
 
            // Calculate the product
            // of a triplet
            long prod = arr[end] * 
                        arr[start] * 
                        arr[mid];
 
            // Check if that product 
            // is greater than m,
            // decrement mid
            if (prod > m)
                mid--;
 
            // Check if that product 
            // is smaller than m,
            // increment start
            else if (prod < m)
                start++;
 
            // Check if that product 
            // is equal to m, 
            // decrement mid, increment
            // start and increment the 
            // count of pairs
            else if (prod == m) 
            {
                count++;
                mid--;
                start++;
            }
        }
    }
 
    return count;
}
 
// Driver code
public static void Main (String []args) 
{
    int []arr = { 1, 1, 1, 1, 1, 1 };
    int n = arr.Length;
    int m = 1;
     
    Console.WriteLine(countTriplets(arr, n, m));
}
}
 
// This code is contributed
// by Arnab Kundu

PHP

<?php
// PHP  implementation of above approach 
 
// Function to count such triplets 
 
function  countTriplets($arr, $n, $m) 
{ 
     $count = 0; 
 
    // Sort the array 
    sort($arr); 
    $end; $start; $mid; 
 
    // three pointer technique 
    for ($end = $n - 1; $end >= 2; $end--) { 
         $start = 0;
         $mid = $end - 1; 
        while ($start < $mid) { 
 
            // Calculate the product of a triplet 
            $prod = $arr[$end] * $arr[$start] * $arr[$mid]; 
 
            // Check if that product is greater than m, 
            // decrement mid 
            if ($prod > $m) 
                $mid--; 
 
            // Check if that product is smaller than m,
            // increment start 
            else if ($prod < $m) 
                $start++; 
 
            // Check if that product is equal to m,
            // decrement mid, increment start and 
            // increment the count of pairs 
            else if ($prod == $m) { 
                $count++; 
                $mid--; 
                $start++; 
            } 
        } 
    } 
 
    return $count; 
} 
 
// Drivers code 
  
    $arr = array( 1, 1, 1, 1, 1, 1 ); 
     $n = sizeof($arr) / sizeof($arr[0]); 
    $m = 1; 
 
    echo  countTriplets($arr, $n, $m); 
 
 
#This Code is Contributed by ajit
?>

Javascript

<script>
 
    // Javascript implementation of above approach
     
    // Function to count such triplets
    function countTriplets(arr, n, m)
    {
        let count = 0;
 
        // Sort the array
        arr.sort(function(a, b){return a - b});
        let end, start, mid;
 
        // three pointer technique
        for (end = n - 1; end >= 2; end--) 
        {
            start = 0; mid = end - 1;
            while (start < mid)
            {
 
                // Calculate the product
                // of a triplet
                let prod = arr[end] * arr[start] * arr[mid];
 
                // Check if that product 
                // is greater than m,
                // decrement mid
                if (prod > m)
                    mid--;
 
                // Check if that product 
                // is smaller than m,
                // increment start
                else if (prod < m)
                    start++;
 
                // Check if that product 
                // is equal to m, 
                // decrement mid, increment
                // start and increment the 
                // count of pairs
                else if (prod == m) 
                {
                    count++;
                    mid--;
                    start++;
                }
            }
        }
 
        return count;
    }
     
    let arr = [ 1, 1, 1, 1, 1, 1 ];
    let n = arr.length;
    let m = 1;
       
    document.write(countTriplets(arr, n, m));
 
</script>

Output

Complexity Analysis:

Time complexity: O(N^2)
Space Complexity: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!