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 tripletsint 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 codeint 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 approachimport java.io.*;import java.util.*;class GFG {// Function to count such tripletsstatic 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 codepublic 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 tripletsdef 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 codeif __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 approachusing System;class GFG {// Function to count such tripletsstatic 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 codepublic 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
6
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
