Dada una array ordenada arr[] que consta de N enteros positivos y un entero D , la tarea es encontrar el número de tripletes (i, j, k) tales que arr[j] – arr[i] = D y arr[k ] – arr[j] = re y 0 ≤ yo < j < k < norte .
Ejemplos:
Entrada: arr[] = {1, 2, 4, 5, 7, 8, 10}, D = 3
Salida: 3
Explicación:
Los siguientes son los tripletes cuya diferencia entre los elementos adyacentes es D(= 3) son:
- {1, 4, 7}
- {4, 7, 10}
- {2, 5, 8}
Por lo tanto, el conteo total de trillizos es 3.
Entrada: arr[] = {1, 2, 4, 5, 7, 8, 10}, D = 1
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los tripletes de la array dada y contar esos tripletes cuya diferencia entre los elementos adyacentes es D(= 3).
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar considerando cada elemento de la array como el último elemento del triplete y verificando los dos elementos anteriores, es decir, (arr[i] – D) y (arr[i] – 2 * D) existe en la array o no. Siga los pasos a continuación para resolver el problema.
- Inicialice un HashMap , digamos M que almacena la frecuencia de los elementos de la array.
- Inicialice una variable, digamos ans como 0 .
- Recorra la array dada arr[] y realice los siguientes pasos:
- Incremente la frecuencia de arr[i] en 1 en HashMap M .
- Ahora, verifique si el elemento (arr[i] – D) y (arr[i] – 2 * D) están presentes en HashMap o no . Si se determina que es verdadero , entonces incremente el valor de ans por freq[arr[i] – D] * freq[arr[i] – 2 * D] .
- Después de completar los pasos anteriores, imprima el valor de ans como el conteo resultante de tripletes en la array.
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 the number of
// triplets having difference
// between adjacent elements equal to D
int countTriplets(int D, vector<int>& arr)
{
// Stores the frequency
// of array elements
unordered_map<int, int> freq;
// Stores the count of
// resultant triplets
int ans = 0;
// Traverse the array
for (int i = 0; i < arr.size(); i++) {
// Check if arr[i] - D and
// arr[i] - 2 * D exists
// in the Hashmap or not
if (freq.find(arr[i] - D)
!= freq.end()
&& freq.find(arr[i] - 2 * D)
!= freq.end()) {
// Update the value of ans
ans += freq[arr[i] - D]
* freq[arr[i] - 2 * D];
}
// Increase the frequency
// of the current element
freq[arr[i]]++;
}
// Return the resultant count
return ans;
}
// Driver Code
int main()
{
vector<int> arr{ 1, 2, 4, 5, 7, 8, 10 };
int D = 1;
cout << countTriplets(D, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count the number of
// triplets having difference
// between adjacent elements equal to D
static int countTriplets(int D, int []arr)
{
// Stores the frequency
// of array elements
HashMap<Integer,
Integer> freq = new HashMap<Integer,
Integer>();
// Stores the count of
// resultant triplets
int ans = 0;
// Traverse the array
for(int i = 0; i < arr.length; i++)
{
// Check if arr[i] - D and
// arr[i] - 2 * D exists
// in the Hashmap or not
if (freq.containsKey(arr[i] - D) &&
freq.containsKey(arr[i] - 2 * D))
{
// Update the value of ans
ans += freq.get(arr[i] - D) *
freq.get(arr[i] - 2 * D);
}
// Increase the frequency
// of the current element
if (freq.containsKey(arr[i]))
{
freq.put(arr[i], freq.get(arr[i]) + 1);
}
else
{
freq.put(arr[i], 1);
}
}
// Return the resultant count
return ans;
}
// Driver Code
public static void main(String[] args)
{
int []arr = { 1, 2, 4, 5, 7, 8, 10 };
int D = 1;
System.out.print(countTriplets(D, arr));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to count the number of
# triplets having difference
# between adjacent elements equal to D
def countTriplets(D, arr):
# Stores the frequency
# of array elements
freq = {}
# Stores the count of
# resultant triplets
ans = 0
# Traverse the array
for i in range(len(arr)):
# Check if arr[i] - D and
# arr[i] - 2 * D exists
# in the Hashmap or not
if (((arr[i] - D) in freq) and
(arr[i] - 2 * D) in freq):
# Update the value of ans
ans += (freq[arr[i] - D] *
freq[arr[i] - 2 * D])
# Increase the frequency
# of the current element
freq[arr[i]] = freq.get(arr[i], 0) + 1
# Return the resultant count
return ans
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 4, 5, 7, 8, 10 ]
D = 1
print (countTriplets(D, arr))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the number of
// triplets having difference
// between adjacent elements equal to D
static int countTriplets(int D, int[] arr)
{
// Stores the frequency
// of array elements
Dictionary<int,
int> freq = new Dictionary<int,
int>();
// Stores the count of
// resultant triplets
int ans = 0;
// Traverse the array
for(int i = 0; i < arr.Length; i++)
{
// Check if arr[i] - D and
// arr[i] - 2 * D exists
// in the Hashmap or not
if (freq.ContainsKey(arr[i] - D) &&
freq.ContainsKey(arr[i] - 2 * D))
{
// Update the value of ans
ans += freq[arr[i] - D] *
freq[arr[i] - 2 * D];
}
// Increase the frequency
// of the current element
if (!freq.ContainsKey(arr[i]))
freq[arr[i]] = 0;
freq[arr[i]]++;
}
// Return the resultant count
return ans;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 4, 5, 7, 8, 10 };
int D = 1;
Console.WriteLine(countTriplets(D, arr));
}
}
// This code is contributed by ukasp
Javascript
<script>
// javascript program for the above approach
// Function to count the number of
// triplets having difference
// between adjacent elements equal to D
function countTriplets(D, arr)
{
// Stores the frequency
// of array elements
var freq = new Map();
// Stores the count of
// resultant triplets
var ans = 0;
var i;
// Traverse the array
for (i = 0; i < arr.length; i++) {
// Check if arr[i] - D and
// arr[i] - 2 * D exists
// in the Hashmap or not
if (freq.has(arr[i] - D) && freq.has(arr[i] - 2 * D)) {
// Update the value of ans
ans += freq.get(arr[i] - D) * freq.get(arr[i] - 2 * D);
}
// Increase the frequency
// of the current element
freq.set(arr[i],freq.get(arr[i])+1);
}
// Return the resultant count
return ans;
}
// Driver Code
var arr = [1, 2, 4, 5, 7, 8, 10];
var D = 1;
document.write(countTriplets(D, arr));
</script>
Producción:
0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA