Count the elements having frequency equals to its value

0 0 11 minutes read

Given an array of integers arr[] of size N, the task is to count all the elements of the array which have a frequency equals to its value.

Examples:

Input: arr[] = {3, 2, 2, 3, 4, 3}
Output: 2
Frequency of element 2 is 2
Frequency of element 3 is 3
Frequency of element 4 is 1
2 and 3 are elements which have same frequency as it’s value

Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: 1

Approach: Store the frequency of every element of the array using the map, and finally count all of that elements whose frequency is equal to their value.

Below is the implementation of the above approach:

C++

// C++ program to count the elements
// having frequency equals to its value
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count
int find_maxm(int arr[], int n)
{
    // Hash map for counting frequency
    map<int, int> mpp;
 
    for (int i = 0; i < n; i++) {
 
        // Counting freq of each element
        mpp[arr[i]] += 1;
    }
 
    int ans = 0;
    for (auto x : mpp) {
        int value = x.first;
        int freq = x.second;
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq) {
            ans++;
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 2, 2, 3, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << find_maxm(arr, n);
 
    return 0;
}

Java

// Java program to count the elements
// having frequency equals to its value
import java.util.*;
 
class GFG{
  
// Function to find the count
static int find_maxm(int arr[], int n)
{
    // Hash map for counting frequency
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
  
    for (int i = 0; i < n; i++) {
  
        // Counting freq of each element
        if(mp.containsKey(arr[i])){
            mp.put(arr[i], mp.get(arr[i])+1);
        }else{
            mp.put(arr[i], 1);
    }
    }
  
    int ans = 0;
    for (Map.Entry<Integer,Integer> x : mp.entrySet()){
        int value = x.getKey();
        int freq = x.getValue();
  
        // Check if value equals to frequency
        // and increment the count
        if (value == freq) {
            ans++;
        }
    }
  
    return ans;
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 2, 2, 3, 4, 3 };
    int n = arr.length;
  
    // Function call
    System.out.print(find_maxm(arr, n)); 
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program to count the elements
# having frequency equals to its value
 
# Function to find the count
def find_maxm(arr, n):
     
    # Hash map for counting frequency
    mpp = {}
     
    for i in range (0, n):
         
        # Counting freq of each element
        if arr[i] in mpp:
            mpp[arr[i]] = mpp[arr[i]] + 1
        else:
            mpp[arr[i]] = 1
     
    ans = 0
     
    for key in mpp:
        value = key
        freq = mpp[key]
         
        # Check if value equals to frequency
        # and increment the count
        if value == freq:
            ans = ans + 1
     
    return ans
 
# Driver code
if __name__ == "__main__":
     
    arr = [ 3, 2, 2, 3, 4, 3 ]
    n = len(arr)
     
    # Function call
    print(find_maxm(arr, n))
   
# This code is contributed by akhilsaini

C#

// C# program to count the elements
// having frequency equals to its value
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to find the count
static int find_maxm(int []arr, int n)
{
    // Hash map for counting frequency
    Dictionary<int,int> mp = new Dictionary<int,int>();
   
    for (int i = 0; i < n; i++) {
   
        // Counting freq of each element
        if(mp.ContainsKey(arr[i])){
            mp[arr[i]] = mp[arr[i]] + 1;
        }else{
            mp.Add(arr[i], 1);
    }
    }
   
    int ans = 0;
    foreach (KeyValuePair<int,int> x in mp){
        int value = x.Key;
        int freq = x.Value;
   
        // Check if value equals to frequency
        // and increment the count
        if (value == freq) {
            ans++;
        }
    }
   
    return ans;
}
   
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 2, 2, 3, 4, 3 };
    int n = arr.Length;
   
    // Function call
    Console.Write(find_maxm(arr, n)); 
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// JavaScript program to count the elements
// having frequency equals to its value
 
 
// Function to find the count
function find_maxm(arr, n)
{
    // Hash map for counting frequency
    let mpp = new Map();
 
    for (let i = 0; i < n; i++) {
 
        // Counting freq of each element
        if(mpp.has(arr[i])){
            mpp.set(arr[i], mpp.get(arr[i]) + 1)
        }else{
            mpp.set(arr[i], 1)
        }
    }
 
    let ans = 0;
    for (let x of mpp) {
        let value = x[0];
        let freq = x[1];
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq) {
            ans++;
        }
    }
 
    return ans;
}
 
// Driver code
 
let arr = [ 3, 2, 2, 3, 4, 3 ];
let n = arr.length;
 
// Function call
document.write(find_maxm(arr, n));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output:

Time complexity: O(n log n)

Space complexity: O(n)

Method #2:Using collections.Counter()

We can solve this problem quickly using python Counter() method. Approach is very simple.

First create a dictionary using Counter method having elements as keys and their frequencies as values
count all of that elements whose frequency is equal to their value(key)

Below is the implementation of above approach:

C++

/* C++ program to count the elements
having frequency equals to its value */
#include <iostream>
#include <unordered_map>
using namespace std;
 
// Function to find the count
int findElements(int arr[], int n)
{
 
  // Create an unordered map using STL which will have
  // elements as keys and their frequencies as values
  unordered_map<int, int> Element_Counter;
  for (int i = 0; i < n; i++) {
    Element_Counter[arr[i]]++;
  }
 
  int ans = 0;
 
  for (auto const& x : Element_Counter) {
    int value = x.first;
    int freq = x.second;
 
    // Check if value equals to frequency and increment
    // the count
    if (value == freq) {
      ans++;
    }
  }
 
  return ans;
}
 
// Driver code
int main()
{
  int arr[] = { 3, 2, 2, 3, 4, 3 };
  int n = sizeof(arr) / sizeof(arr[0]);
 
  // Function call
  cout << findElements(arr, n) << endl;
 
  return 0;
}
 
// This code is contributed by phasing17.

Java

// Java program to count the elements
// having frequency equals to its value
import java.util.HashMap;
import java.util.Map;
 
public class Main {
 
    // Function to find the count
    public static int findElements(int[] arr, int n)
    {
        // HashMap to store elements and their frequencies
        Map<Integer, Integer> elementCounter
            = new HashMap<>();
        int ans = 0;
 
        // Store the frequencies of each element in a
        // HashMap
        for (int i = 0; i < n; i++) {
            int key = arr[i];
            if (elementCounter.containsKey(key)) {
                elementCounter.put(
                    key, elementCounter.get(key) + 1);
            }
            else {
                elementCounter.put(key, 1);
            }
        }
 
        // Check if the value of each element is equal to
        // its frequency
        for (Map.Entry<Integer, Integer> entry :
             elementCounter.entrySet()) {
            int value = entry.getKey();
            int freq = entry.getValue();
 
            // If the value of the element is equal to its
            // frequency, increment the count
            if (value == freq) {
                ans++;
            }
        }
        return ans;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 3, 2, 2, 3, 4, 3 };
        int n = arr.length;
 
        // Call the function to find the count
        System.out.println(findElements(arr, n));
    }
}

Python3

# Python3 program to count the elements
# having frequency equals to its value
# importing counter from collections
from collections import Counter
 
# Function to find the count
def findElements(arr, n):
   
    # Now create dictionary using counter method
    # which will have elements as key and their
    # frequencies as values
    Element_Counter = Counter(arr)
    ans = 0
 
    for key in Element_Counter:
        value = key
        freq = Element_Counter[key]
 
        # Check if value equals to frequency
        # and increment the count
        if value == freq:
            ans = ans + 1
 
    return ans
 
 
# Driver code
arr = [3, 2, 2, 3, 4, 3]
n = len(arr)
 
# Function call
print(findElements(arr, n))
 
# This code is contributed by vikkycirus

C#

// C# program to count the elements
// having frequency equals to its value
using System;
using System.Collections.Generic;
 
public class MainClass
{
   
  // Function to find the count
  public static int FindElements(int[] arr, int n)
  {
 
    // Dictionary to store elements and their
    // frequencies
    Dictionary<int, int> elementCounter
      = new Dictionary<int, int>();
    int ans = 0;
 
    // Store the frequencies of each element in a
    // Dictionary
    for (int i = 0; i < n; i++)
    {
      int key = arr[i];
      if (elementCounter.ContainsKey(key)) {
        elementCounter[key]
          = elementCounter[key] + 1;
      }
      else {
        elementCounter.Add(key, 1);
      }
    }
 
    // Check if the value of each element is equal to
    // its frequency
    foreach(
      KeyValuePair<int, int> entry in elementCounter)
    {
      int value = entry.Key;
      int freq = entry.Value;
 
      // If the value of the element is equal to its
      // frequency, increment the count
      if (value == freq) {
        ans++;
      }
    }
    return ans;
  }
 
  public static void Main()
  {
    int[] arr = { 3, 2, 2, 3, 4, 3 };
    int n = arr.Length;
 
    // Call the function to find the count
    Console.WriteLine(FindElements(arr, n));
  }
}
 
// This code is contributed by phasing17.

Javascript

/* JavaScript program to count the elements
having frequency equals to its value */
function findElements(arr) {
 
    // Create an object to store the frequency count of each element
    let elementCounter = {};
    for (let i = 0; i < arr.length; i++) {
        if (elementCounter[arr[i]] === undefined) {
            elementCounter[arr[i]] = 1;
        } else {
            elementCounter[arr[i]]++;
        }
    }
 
    let ans = 0;
 
    // Iterate through the object and check if the value equals the key
    for (let key in elementCounter) {
        if (elementCounter.hasOwnProperty(key)) {
            let value = parseInt(key);
            let freq = elementCounter[key];
            // Check if value equals to frequency and increment the count
            if (value === freq) {
                ans++;
            }
        }
    }
 
    return ans;
}
 
// Driver code
let arr = [3, 2, 2, 3, 4, 3];
 
// Function call
console.log(findElements(arr));

Output

Time complexity: O(n), where n is the number of elements in the array

Space complexity: O(n)

Method 3: Using Binary Search

The idea of using Binary Search is that we can use the index values of elements after sorting the array.

If the difference of indices is equal to its value then we can say that the no of appearances of the element is equal to its value.

By this approach, we can reduce the space complexity from O(N) to O(1).

Below is the implementation of the above idea.

C++

#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
 
int binarySearch(int arr[], int target, int left, int right)
{
    int index = -1;
 
    while (left <= right) {
        int middle = left + (right - left) / 2;
 
        // if found, keep searching fwd to the last
        // occurence, otherwise, search to the left
        if (arr[middle] == target) {
            index = middle;
            left = middle + 1;
        }
        else {
            right = middle - 1;
        }
    }
 
    return index;
}
int func(int arr[], int n)
{
    sort(arr,arr+n);
 
    int ans = -1;
    int i = 0;
 
    while (i < n) {
        int current = arr[i];
 
        // search the last occurence from the current index
        int j= binarySearch(arr, current, i,n-1);
 
        // if the number of occurences of current element
        // equal the current element itself, update the
        // magic integer
        if ((j - i) + 1 == current) {
            ans = current;
        }
 
        // move index to the next different element
        i = j + 1;
    }
 
    return ans;
}
 
 
int main()
{
 
    int arr[] = { 4, 3, 3, 2, 4, 4, 9, 7, 8, 4, 2, 2 };
    int n = sizeof(arr) / sizeof(int);
    int ans = func(arr, n);
    if (ans == -1) {
        cout << "There is no such number exists" << endl;
    }
    else {
        cout << "The number is : " << ans << endl;
    }
    return 0;
}
 
//This code is contributed by aeroabrar_31

Java

/*package whatever //do not write package name here */
 
import java.util.*;
 
class GFG {
    public static void main (String[] args) {
        int[] arr = {  4, 3, 3, 2, 4, 4, 9, 7, 8, 4, 2, 2  };
        int n = arr.length;
        int res = func(arr, n);
        if (res == -1) {
            System.out.println("There is no such number exists ! ");
        }
        else {
            System.out.println("The number is : " + res);
        }
         
    }
   
  public static int func(int[] arr,int n) {
        Arrays.sort(arr);
         
        int ans = -1;
        int i = 0;
         
        while(i < arr.length){
            int current = arr[i];
             
            // search the last occurence from the current index
            int j = binarySearch(arr, current, i, arr.length - 1);
             
            // if the number of occurences of current element equal the 
            //current element itself, update the lucky integer
            if((j - i) + 1 == current){
                ans = current;
            }
 
            // move index to the next different element
            i = j + 1;
        }
         
        return ans;
    }
       
      public static int binarySearch(int[] arr, int target, int left, int right){
        int index = -1;
         
        while(left <= right){
            int middle = left + (right - left) / 2;
 
            // if found, keep searching fwd to the last occurence, 
            //otherwise, search to the left
            if(arr[middle] == target){
                index = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
         
        return index;
    }
  
}
 
// This code is contributed by aeroabrar_31

Javascript

function binarySearch(arr, target, left, right) {
    let index = -1;
 
    while (left <= right) {
        let middle = left + Math.floor((right - left) / 2);
 
        // If found, keep searching forward to the last
        // occurrence, otherwise, search to the left
        if (arr[middle] == target) {
            index = middle;
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
 
    return index;
}
 
function func(arr, n) {
    arr.sort((a, b) => a - b);
 
    let ans = -1;
    let i = 0;
 
    while (i < n) {
        let current = arr[i];
 
        // Search the last occurrence from the current index
        let j = binarySearch(arr, current, i, n - 1);
 
        // If the number of occurrences of current element
        // equal the current element itself, update the
        // magic integer
        if ((j - i) + 1 == current) {
            ans = current;
        }
 
        // Move index to the next different element
        i = j + 1;
    }
 
    return ans;
}
 
let arr = [4, 3, 3, 2, 4, 4, 9, 7, 8, 4, 2, 2];
let n = arr.length;
let ans = func(arr, n);
if (ans == -1) {
    console.log("There is no such number exists");
} else {
    console.log("The number is : " + ans);
}

Python3

def binary_search(arr, target, left, right):
    index = -1
     
    while left <= right:
        middle = left + (right - left) // 2
         
        if arr[middle] == target:
            index = middle
            left = middle + 1
        else:
            right = middle - 1
     
    return index
 
def func(arr):
    arr.sort()
     
    ans = -1
    i = 0
     
    while i < len(arr):
        current = arr[i]
        j = binary_search(arr, current, i, len(arr) - 1)
         
        if (j - i) + 1 == current:
            ans = current
         
        i = j + 1
     
    return ans
 
arr = [4, 3, 3, 2, 4, 4, 9, 7, 8, 4, 2, 2]
ans = func(arr)
if ans == -1:
    print("There is no such number exists")
else:
    print("The number is:", ans)
#This code is contributed by Zaid

C#

using System;
 
public class Program {
    static int BinarySearch(int[] arr, int target, int left,
                            int right)
    {
        int index = -1;
 
        while (left <= right) {
            int middle = left + (right - left) / 2;
 
            // if found, keep searching fwd to the last
            // occurence, otherwise, search to the left
            if (arr[middle] == target) {
                index = middle;
                left = middle + 1;
            }
            else {
                right = middle - 1;
            }
        }
 
        return index;
    }
 
    static int Func(int[] arr, int n)
    {
        Array.Sort(arr);
 
        int ans = -1;
        int i = 0;
 
        while (i < n) {
            int current = arr[i];
 
            // search the last occurence
            // from the current index
            int j = BinarySearch(arr, current, i, n - 1);
 
            // if the number of occurences
            // of current element equal the
            // current element itself, update the
            // magic integer
            if ((j - i) + 1 == current) {
                ans = current;
            }
 
            // move index to the next different element
            i = j + 1;
        }
 
        return ans;
    }
 
    public static void Main()
    {
        int[] arr = { 4, 3, 3, 2, 4, 4, 9, 7, 8, 4, 2, 2 };
        int n = arr.Length;
 
        int ans = Func(arr, n);
 
        if (ans == -1) {
            Console.WriteLine(
                "There is no such number exists");
        }
        else {
            Console.WriteLine("The number is: " + ans);
        }
    }
}

Output

The number is : 4

Time Complexity : O ( N * logN )

Auxiliary Space : O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!