|
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++
<?php
function countTriplets($arr, $n, $m)
{
$count = 0;
sort($arr);
$end; $start; $mid;
for ($end = $n - 1; $end >= 2; $end--) {
$start = 0;
$mid = $end - 1;
while ($start < $mid) {
$prod = $arr[$end] * $arr[$start] * $arr[$mid];
if ($prod > $m)
$mid--;
else if ($prod < $m)
$start++;
else if ($prod == $m) {
$count++;
$mid--;
$start++;
}
}
}
return $count;
}
$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>
function countTriplets(arr, n, m)
{
let count = 0;
arr.sort(function(a, b){return a - b});
let end, start, mid;
for (end = n - 1; end >= 2; end--)
{
start = 0; mid = end - 1;
while (start < mid)
{
let prod = arr[end] * arr[start] * arr[mid];
if (prod > m)
mid--;
else if (prod < m)
start++;
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>
|
Complexity Analysis:
- Time complexity: O(N^2)
- Space Complexity: O(1)
|
