Cuente los tripletes de una array ordenada que tenga una diferencia entre los elementos adyacentes igual a D

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. {1, 4, 7}
  2. {4, 7, 10}
  3. {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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *