Cuente cuádruples (i, j, k, l) en una array tal que i < j < k < l y arr[i] = arr[k] y arr[j] = arr[l]

Dada una array arr[] que consiste en N enteros, la tarea es contar el número de tuplas (i, j, k, l) de la array dada tal que i < j < k < l y arr[i] = arr[ k] y arr[j] = arr[l] .

Ejemplos:

Entrada: arr[] = {1, 2, 1, 2, 2, 2} 
Salida: 4 
Explicación: 
Las tuplas que cumplen la condición dada son: 
1) (0, 1, 2, 3) ya que arr[0] = arr[2] = 1 y arr[1] = arr[3] = 2 
2) (0, 1, 2, 4) ya que arr[0] = arr[2] = 1 y arr[1] = arr[4 ] = 2 
3) (0, 1, 2, 5) ya que arr[0] = arr[2] = 1 y arr[1] = arr[5] = 2 
4) (1, 3, 4, 5) ya que array[1] = array[4] = 2 y array[3] = array[5] = 2

Entrada: arr[] = {2, 5, 2, 2, 5, 4} 
Salida: 2

Enfoque ingenuo: el enfoque más simple es generar todos los cuádruples posibles y verificar si la condición dada se cumple. Si se determina que es cierto, aumente el recuento final. Imprime el conteo final obtenido.

Complejidad de Tiempo: O(N ⁴ ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Hashing . A continuación se muestran los pasos:

1. Para cada índice j iterar para encontrar un par de índices (j, l) tales que arr[j] = arr[l] y j < l .
2. Use una tabla hash para llevar la cuenta de la frecuencia de todos los elementos de la array presentes en los índices [0, j – 1] .
3. Mientras atraviesa el índice j a l , simplemente agregue la frecuencia de cada elemento entre j y l al conteo final.
4. Repita este proceso para cada posible par de índices (j, l) .
5. Imprima el recuento total de cuádruples después de los pasos anteriores.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count total number
// of required tuples
int countTuples(int arr[], int N)
{
    int ans = 0, val = 0;
 
    // Initialize unordered map
    unordered_map<int, int> freq;
 
    for (int j = 0; j < N - 2; j++) {
        val = 0;
 
        // Find the pairs (j, l) such
        // that arr[j] = arr[l] and j < l
        for (int l = j + 1; l < N; l++) {
 
            // elements are equal
            if (arr[j] == arr[l]) {
 
                // Update the count
                ans += val;
            }
 
            // Add the frequency of
            // arr[l] to val
            val += freq[arr[l]];
        }
 
        // Update the frequency of
        // element arr[j]
        freq[arr[j]]++;
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, 1, 2, 2, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << countTuples(arr, N);
 
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to count total number
// of required tuples
static int countTuples(int arr[],
                       int N)
{
  int ans = 0, val = 0;
 
  // Initialize unordered map
  HashMap<Integer,
          Integer> freq = new HashMap<Integer,
                                      Integer>();
 
  for (int j = 0; j < N - 2; j++)
  {
    val = 0;
 
    // Find the pairs (j, l) such
    // that arr[j] = arr[l] and j < l
    for (int l = j + 1; l < N; l++)
    {
      // elements are equal
      if (arr[j] == arr[l])
      {
        // Update the count
        ans += val;
      }
 
      // Add the frequency of
      // arr[l] to val
      if(freq.containsKey(arr[l]))
        val += freq.get(arr[l]);
    }
 
    // Update the frequency of
    // element arr[j]
    if(freq.containsKey(arr[j]))
    {
      freq.put(arr[j], freq.get(arr[j]) + 1);
    }
    else
    {
      freq.put(arr[j], 1);
    }
  }
 
  // Return the answer
  return ans;
}
 
// Driver code
public static void main(String[] args)
{
  // Given array arr[]
  int arr[] = {1, 2, 1, 2, 2, 2};
  int N = arr.length;
 
  // Function Call
  System.out.print(countTuples(arr, N));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to count total number
# of required tuples
def countTuples(arr, N):
     
    ans = 0
    val = 0
 
    # Initialize unordered map
    freq = {}
 
    for j in range(N - 2):
        val = 0
 
        # Find the pairs (j, l) such
        # that arr[j] = arr[l] and j < l
        for l in range(j + 1, N):
 
            # Elements are equal
            if (arr[j] == arr[l]):
 
                # Update the count
                ans += val
 
            # Add the frequency of
            # arr[l] to val
            if arr[l] in freq:
                val += freq[arr[l]]
 
        # Update the frequency of
        # element arr[j]
        freq[arr[j]] = freq.get(arr[j], 0) + 1
 
    # Return the answer
    return ans
 
# Driver code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 1, 2, 1, 2, 2, 2 ]
 
    N = len(arr)
 
    # Function call
    print(countTuples(arr, N))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count total number
// of required tuples
static int countTuples(int []arr,
                       int N)
{
    int ans = 0, val = 0;
     
    // Initialize unordered map
    Dictionary<int,
               int> freq = new Dictionary<int,
                                          int>();
     
    for(int j = 0; j < N - 2; j++)
    {
        val = 0;
         
        // Find the pairs (j, l) such
        // that arr[j] = arr[l] and j < l
        for(int l = j + 1; l < N; l++)
        {
             
            // Elements are equal
            if (arr[j] == arr[l])
            {
                 
                // Update the count
                ans += val;
            }
             
            // Add the frequency of
            // arr[l] to val
            if (freq.ContainsKey(arr[l]))
                val += freq[arr[l]];
        }
         
        // Update the frequency of
        // element arr[j]
        if (freq.ContainsKey(arr[j]))
        {
            freq[arr[j]] = freq[arr[j]] + 1;
        }
        else
        {
            freq.Add(arr[j], 1);
        }
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 1, 2, 1, 2, 2, 2 };
    int N = arr.Length;
     
    // Function call
    Console.Write(countTuples(arr, N));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript program for the above approach
 
// Function to count total number
// of required tuples
function countTuples(arr, N)
{
    var ans = 0, val = 0;
 
    // Initialize unordered map
    var freq = new Map();
 
    for(var j = 0; j < N - 2; j++)
    {
        val = 0;
 
        // Find the pairs (j, l) such
        // that arr[j] = arr[l] and j < l
        for(var l = j + 1; l < N; l++)
        {
             
            // Elements are equal
            if (arr[j] == arr[l])
            {
                 
                // Update the count
                ans += val;
            }
 
            // Add the frequency of
            // arr[l] to val
            if (freq.has(arr[l]))
            {
                val += freq.get(arr[l]);
            }
        }
 
        // Update the frequency of
        // element arr[j]
        if (freq.has(arr[j]))
        {
            freq.set(arr[j], freq.get(arr[j]) + 1);
        }
        else
        {
            freq.set(arr[j], 1);
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
 
// Given array arr[]
var arr = [ 1, 2, 1, 2, 2, 2 ];
var N = arr.length;
 
// Function Call
document.write(countTuples(arr, N));
 
// This code is contributed by rutvik_56
 
</script>

4

Tiempo Complejidad: O(N ² ) 
Espacio Auxiliar: O(N)