Dada una array arr[] de N enteros, la tarea es contar el número de tripletes (i, j, k) en la array tal que a[k] < a[i] < a[j] e i < j < k .
Ejemplos:
Entrada: arr[] = {2, 5, 1, 3, 0}
Salida: 4
Explicación:
A continuación se muestran los tripletes (i, j, k) tales que i < j < k y a[k] < a[i] < a[j] :
1. (0, 1, 2) y arr[2] < arr[0] 1 < 2 < 5.
2. (0, 1, 4) y arr[4] < arr[0] 0 < 2 < 5.
3. (0, 3, 4) y arr[4] < arr[0] 0 < 2 < 3.
4. (2, 3, 4) y arr[4] < arr[2] 0 < 1 < 3.
Entrada: arr[] = {2, 5, 1, 2, 0, 3, 10, 1, 5, 0 }
Salida: 25
Enfoque ingenuo: la idea es iterar 3 bucles y verificar que cada triplete (i, j, k) satisfaga o no las condiciones dadas. En caso afirmativo, incremente para ese triplete e imprima el conteo final después de verificar todos los tripletes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count triplets with the
// given conditions
int CountTriplets(int arr[], int n)
{
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
// If it satisfy the
// given conditions
if (arr[k] < arr[i]
&& arr[i] < arr[j]) {
cnt += 1;
}
// Return the final count
return cnt;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 5, 1, 3, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << CountTriplets(arr, n)
<< endl;
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to count triplets
// with the given conditions
static int CountTriplets(int arr[], int n)
{
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
for(int k = j + 1; k < n; k++)
// If it satisfy the
// given conditions
if (arr[k] < arr[i] &&
arr[i] < arr[j])
{
cnt += 1;
}
// Return the final count
return cnt;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = new int[]{ 2, 5, 1, 3, 0 };
int n = arr.length;
System.out.print(CountTriplets(arr, n));
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 program for the above approach # Function to count triplets with the # given conditions def CountTriplets(arr, n): cnt = 0; for i in range(0, n): for j in range(i + 1, n): for k in range(j + 1, n): # If it satisfy the # given conditions if (arr[k] < arr[i] and arr[i] < arr[j]): cnt += 1; # Return the final count return cnt; # Driver Code # Given array arr[] arr = [ 2, 5, 1, 3, 0 ]; n = len(arr); # Function Call print(CountTriplets(arr, n)) # This code is contributed by Code_Mech
C#
// C# program for the above approach
using System;
class GFG{
// Function to count triplets
// with the given conditions
static int CountTriplets(int []arr, int n)
{
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
for(int k = j + 1; k < n; k++)
// If it satisfy the
// given conditions
if (arr[k] < arr[i] &&
arr[i] < arr[j])
{
cnt += 1;
}
// Return the final count
return cnt;
}
// Driver Code
public static void Main(string[] args)
{
// Given array arr[]
int []arr = new int[]{ 2, 5, 1, 3, 0 };
int n = arr.Length;
Console.Write(CountTriplets(arr, n));
}
}
// This code is contributed by Ritik Bansal
Javascript
<script>
// Javascript program for the above approach
// Function to count triplets with the
// given conditions
function CountTriplets(arr, n)
{
let cnt = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
for (let k = j + 1; k < n; k++)
// If it satisfy the
// given conditions
if (arr[k] < arr[i]
&& arr[i] < arr[j]) {
cnt += 1;
}
// Return the final count
return cnt;
}
// Given array arr[]
let arr = [ 2, 5, 1, 3, 0 ];
let n = arr.length;
// Function Call
document.write(CountTriplets(arr, n));
</script>
Producción:
4
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: podemos reducir la complejidad de N ^ 3 a N ^ 2, siguiendo los pasos a continuación:
- Ejecute dos ciclos para encontrar pares (i, j) tales que i < j y arr[j] > arr[i] y mantenga la cuenta de estos pares como cnt .
- Mientras que en el ciclo anterior, si existe algún elemento como arr[j] < arr[i] , incremente el conteo de tripletes por cnt ya que el elemento actual es el K-ésimo elemento tal que a[k] <a[i] <a[ j] para el triplete i < j < k .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count triplets
int CountTriplets(int a[], int n)
{
// To store count of total triplets
int ans = 0;
for (int i = 0; i < n; i++) {
// Initialize count to zero
int cnt = 0;
for (int j = i + 1; j < n; j++) {
// If a[j] > a[i] then,
// increment cnt
if (a[j] > a[i])
cnt++;
// If a[j] < a[i], then
// it mean we have found a[k]
// such that a[k] < a[i] < a[j]
else
ans += cnt;
}
}
// Return the final count
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 5, 1, 3, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << CountTriplets(arr, n) << endl;
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to count triplets
static int CountTriplets(int a[], int n)
{
// To store count of total triplets
int ans = 0;
for (int i = 0; i < n; i++)
{
// Initialize count to zero
int cnt = 0;
for (int j = i + 1; j < n; j++)
{
// If a[j] > a[i] then,
// increment cnt
if (a[j] > a[i])
cnt++;
// If a[j] < a[i], then
// it mean we have found a[k]
// such that a[k] < a[i] < a[j]
else
ans += cnt;
}
}
// Return the final count
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 5, 1, 3, 0 };
int n = arr.length;
System.out.print(CountTriplets(arr, n));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program for # the above approach # Function to count triplets def CountTriplets(a, n): # To store count # of total triplets ans = 0 for i in range (n): # Initialize count to zero cnt = 0 for j in range (i + 1 , n): # If a[j] > a[i] then, # increment cnt if (a[j] > a[i]): cnt += 1 # If a[j] < a[i], then # it mean we have found a[k] # such that a[k] < a[i] < a[j] else: ans += cnt # Return the final count return ans # Driver code if __name__ == "__main__": arr = [2, 5, 1, 3, 0] n = len(arr) print (CountTriplets(arr, n)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to count triplets
static int CountTriplets(int []a, int n)
{
// To store count of total triplets
int ans = 0;
for (int i = 0; i < n; i++)
{
// Initialize count to zero
int cnt = 0;
for (int j = i + 1; j < n; j++)
{
// If a[j] > a[i] then,
// increment cnt
if (a[j] > a[i])
cnt++;
// If a[j] < a[i], then
// it mean we have found a[k]
// such that a[k] < a[i] < a[j]
else
ans += cnt;
}
}
// Return the final count
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 2, 5, 1, 3, 0 };
int n = arr.Length;
Console.Write(CountTriplets(arr, n));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program for the above approach
// Function to count triplets
function CountTriplets(a, n)
{
// To store count of total triplets
let ans = 0;
for(let i = 0; i < n; i++)
{
// Initialize count to zero
let cnt = 0;
for(let j = i + 1; j < n; j++)
{
// If a[j] > a[i] then,
// increment cnt
if (a[j] > a[i])
cnt++;
// If a[j] < a[i], then
// it mean we have found a[k]
// such that a[k] < a[i] < a[j]
else
ans += cnt;
}
}
// Return the final count
return ans;
}
// Driver code
let arr = [ 2, 5, 1, 3, 0 ];
let n = arr.length;
document.write(CountTriplets(arr, n));
// This code is contributed by rameshtravel07
</script>
Producción:
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA