Dada una array de enteros distintos (considerando solo números positivos) y un número ‘m’, encuentre el número de tripletes con el producto igual a ‘m’.
Ejemplos:
Input: arr[] = { 1, 4, 6, 2, 3, 8}
m = 24
Output: 3
Input: arr[] = { 0, 4, 6, 2, 3, 8}
m = 18
Output: 0
Ya se ha discutido un enfoque con O (n) espacio adicional en una publicación anterior . En esta publicación se discutirá un enfoque con complejidad espacial O(1).
Enfoque: La idea es utilizar la técnica de los tres puntos:
- Ordenar la array de entrada.
- Fije el primer elemento como A[i] donde i es de 0 a tamaño de array – 2.
- Después de arreglar el primer elemento del triplete, encuentre los otros dos elementos usando la técnica de 2 punteros.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
6
Complejidad temporal: O(N^2)
Complejidad espacial: O(1)
Publicación traducida automáticamente
Artículo escrito por agnivakolay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA