Cuente los pares en una array de modo que la frecuencia de uno sea al menos el valor del otro

Dada una array A[] de enteros. La tarea es encontrar el número total de pares ordenados de enteros positivos (X, Y) tales que X aparezca en A[] al menos Y veces e Y aparezca en A al menos X veces.
Ejemplos : 
 

Input : A[] = { 1, 1, 2, 2, 3 }
Output : 4
Ordered pairs are -> { [1, 1], [1, 2], [2, 1], [2, 2] }

Input : A = { 3, 3, 2, 2, 2 }
Output : 3
Ordered pairs are -> { [3, 2], [2, 2], [2, 3] }

Acercarse: 
 

1. Cree una tabla hash m[] de recuento de elementos de la array A[].
2. Atraviesa la tabla hash de elementos únicos. Sea X la clave actual en la tabla hash y sea su frecuencia.
3. Verifique para cada elemento j = (1 a Y) tal que, si m[ j ] >= X incremente la respuesta en 1.
4. Devuelve el recuento de pares ordenados totales (X, Y) de la array A.

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

// C++ program to find number
// of ordered pairs
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find count of Ordered pairs
int countOrderedPairs(int A[], int n)
{
    // Initialize pairs to 0
    int orderedPairs = 0;
 
    // Store frequencies
    unordered_map<int, int> m;
    for (int i = 0; i < n; ++i)
        m[A[i]]++;
     
    // Count total Ordered_pairs
    for (auto entry : m) {
        int X = entry.first;
        int Y = entry.second;
 
        for (int j = 1; j <= Y; j++) {
            if (m[j] >= X)
                orderedPairs++;
        }
    }
 
    return orderedPairs;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 1, 2, 2, 3 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << countOrderedPairs(A, n);
    return 0;
}

// Java program to find number
// of ordered pairs
import java.util.HashMap;
import java.util.Map;
 
class GFG
{
     
    // Function to find count of Ordered pairs
    public static int countOrderedPairs(int[] A, int n)
    {
 
        // Initialize pairs to 0
        int orderedPairs = 0;
 
        // Store frequencies
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            if (m.get(A[i]) == null)
                m.put(A[i], 1);
            else
            {
                int a = m.get(A[i]);
                m.put(A[i], ++a);
            }
        }
 
        // Count total Ordered_pairs
        for (int entry : m.keySet())
        {
             
            int X = entry;
            int Y = m.get(entry);
 
            for (int j = 1; j <= Y; j++)
            {
                if (m.get(j) >= X)
                    orderedPairs++;
            }
        }
 
        return orderedPairs;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] A = {1, 1, 2, 2, 3};
        int n = A.length;
        System.out.print(countOrderedPairs(A, n));
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 program to find the
# number of ordered pairs
from collections import defaultdict
 
# Function to find count of Ordered pairs
def countOrderedPairs(A, n):
 
    # Initialize pairs to 0
    orderedPairs = 0
 
    # Store frequencies
    m = defaultdict(lambda:0)
    for i in range(0, n):
        m[A[i]] += 1
     
    # Count total Ordered_pairs
    for X,Y in m.items():
         
        for j in range(1, Y + 1):
            if m[j] >= X:
                orderedPairs += 1
         
    return orderedPairs
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 1, 2, 2, 3]
    n = len(A)
    print(countOrderedPairs(A, n))
     
# This code is contributed by Rituraj Jain

// C# program to illustrate how
// to create a dictionary
using System;
using System.Collections.Generic;
 
class GFG
{
     
    // Function to find count of Ordered pairs
    public static int countOrderedPairs(int[] A,           
                                        int n)
    {
 
        // Initialize pairs to 0
        int orderedPairs = 0;
 
        // Store frequencies
        Dictionary<int,    
                   int> m = new Dictionary<int,
                                           int>();
        for (int i = 0; i < n; i++)
        {
            if (!m.ContainsKey(A[i]))
                m.Add(A[i], 1);
            else
            {
                m[A[i]]++;
            }
        }
 
        // Count total Ordered_pairs
        foreach(KeyValuePair<int, int> entry in m)
        {
             
            int X = entry.Key;
            int Y = entry.Value;
 
            for (int j = 1; j <= Y; j++)
            {
                if (m[j] >= X)
                    orderedPairs++;
            }
        }
        return orderedPairs;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] A = {1, 1, 2, 2, 3};
        int n = A.Length;
        Console.Write(countOrderedPairs(A, n));
    }
}
 
// This code is contributed by
// mohit kumar

<script>
 
// JavaScript program to find number
// of ordered pairs
 
// Function to find count of Ordered pairs
function countOrderedPairs(A, n)
{
    // Initialize pairs to 0
    let orderedPairs = 0;
 
    // Store frequencies
    let m = new Map();
    for (let i = 0; i < n; ++i){
        if(m.has(A[i])){
            m.set(A[i],m.get(A[i])+1);
        }
        else m.set(A[i],1);
    }
     
    // Count total Ordered_pairs
    for (let [key,value] of m) {
        let X = key;
        let Y = value;
 
        for (let j = 1; j <= Y; j++) {
            if (m.get(j) >= X)
                orderedPairs++;
        }
    }
 
    return orderedPairs;
}
 
// Driver Code
let A =[ 1, 1, 2, 2, 3 ];
let n = A.length;
document.write(countOrderedPairs(A, n));
 
// This code is contributed by shinjanpatra
 
</script>

4

Complejidad de tiempo: O(n), para recorrer el interior del mapa pares clave-valor
Espacio auxiliar: O(n), para crear un mapa de tamaño n