Cuente los elementos que tienen una frecuencia igual a su valor | conjunto 2

Dada una array de enteros arr[] de tamaño N , la tarea es contar todos los elementos de la array que tienen una frecuencia igual a su valor.
Ejemplos: 

Entrada: arr[] = {3, 2, 2, 3, 4, 3} 
Salida: 2 
Explicación: 
La frecuencia del elemento 2 es 2 
La frecuencia del elemento 3 es 3 
La frecuencia del elemento 4 es 1 
2 y 3 son elementos que tienen el mismo frecuencia como su valor 

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

Enfoque:  siga los pasos a continuación para resolver el problema: 

1. Almacene las frecuencias de cada elemento de la array con el valor menor que igual al tamaño de array dado en la array freq[] .
2. La razón del paso anterior es que la frecuencia de un elemento puede ser como máximo igual al tamaño de la array dada. Por lo tanto, no hay necesidad de almacenar la frecuencia de un elemento, cuyo valor es mayor que el tamaño de array dado.
3. Cuente los números enteros que tienen frecuencias iguales a su valor.
4. Imprime el conteo final.

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

// C++ program of the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the integer
// which has a frequency in the
// array equal to its value.
void solve(int arr[], int n)
{
    // Store frequency of array
    // elements
    int freq[n+1] ={0};
 
    for (int i = 0; i < n; i++) {
 
        // Store the frequency
        // only if arr[i]<=n
        if (arr[i] <= n)
            freq[arr[i]]++;
    }
 
    // Initially the count is zero
    int count = 0;
 
    for (int i = 1; i <= n; i++) {
        // If the freq[i] is equal
        // to i, then increment
        // the count by 1
        if (i == freq[i]) {
            count++;
        }
    }
 
    // Print the final count
    cout << count << "\n";
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 1, 1, 3, 2, 2, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    solve(arr, N);
    return 0;
}

// Java program of the
// above approach
class GFG{
 
// Function to find the integer
// which has a frequency in the
// array equal to its value.
static void solve(int arr[],
                  int n)
{
  // Store frequency of array
  // elements
  int []freq = new int[n + 1];
 
  for (int i = 0; i < n; i++)
  {
    // Store the frequency
    // only if arr[i]<=n
    if (arr[i] <= n)
      freq[arr[i]]++;
  }
 
  // Initially the count is zero
  int count = 0;
 
  for (int i = 1; i <= n; i++)
  {
    // If the freq[i] is equal
    // to i, then increment
    // the count by 1
    if (i == freq[i])
    {
      count++;
    }
  }
 
  // Print the final count
  System.out.print(count + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
  int arr[] = {3, 1, 1, 3, 2, 2, 3};
  int N = arr.length;
  solve(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program of the
# above approach
 
# Function to find the integer
# which has a frequency in the
# array equal to its value.
def solve(arr, n):
   
    # Store frequency of array
    # elements
    freq = [0] * (n + 1);
 
    for i in range(n):
       
        # Store the frequency
        # only if arr[i]<=n
        if (arr[i] <= n):
            freq[arr[i]] += 1;
 
    # Initially the count is zero
    count = 0;
 
    for i in range(1, n + 1):
       
        # If the freq[i] is equal
        # to i, then increment
        # the count by 1
        if (i == freq[i]):
            count += 1;
 
    # Print final count
    print(count , "");
 
 
# Driver Code
if __name__ == '__main__':
   
    arr = [3, 1, 1, 3,
           2, 2, 3];
    N = len(arr);
    solve(arr, N);
 
# This code is contributed by shikhasingrajput

// C# program of the
// above approach
using System;
class GFG{
 
// Function to find the integer
// which has a frequency in the
// array equal to its value.
static void solve(int []arr,
                  int n)
{
  // Store frequency of array
  // elements
  int []freq = new int[n + 1];
 
  for (int i = 0; i < n; i++)
  {
    // Store the frequency
    // only if arr[i]<=n
    if (arr[i] <= n)
      freq[arr[i]]++;
  }
 
  // Initially the count is zero
  int count = 0;
 
  for (int i = 1; i <= n; i++)
  {
    // If the freq[i] is equal
    // to i, then increment
    // the count by 1
    if (i == freq[i])
    {
      count++;
    }
  }
 
  // Print the readonly count
  Console.Write(count + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = {3, 1, 1, 3, 2, 2, 3};
  int N = arr.Length;
  solve(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for
// the above approach
 
// Function to find the integer
// which has a frequency in the
// array equal to its value.
function solve(arr, n)
{
 
  // Store frequency of array
  // elements
  let freq = Array.from({length: n+1}, (_, i) => 0);
  
  for (let i = 0; i < n; i++)
  {
   
    // Store the frequency
    // only if arr[i]<=n
    if (arr[i] <= n)
      freq[arr[i]]++;
  }
  
  // Initially the count is zero
  let count = 0;
  
  for (let i = 1; i <= n; i++)
  {
   
    // If the freq[i] is equal
    // to i, then increment
    // the count by 1
    if (i == freq[i])
    {
      count++;
    }
  }
  
  // Print the final count
  document.write(count + "<br/>");
}
 
// Driver code
     
  let arr = [ 3, 1, 1, 3, 2, 2, 3 ];
  let N = arr.length;
  solve(arr, N);
  
 // This code is contributed by souravghosh0416.
</script>

2

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)

Consulte la publicación anterior para el enfoque O (N * log (N)) .