C program to count frequency of each element in an array

0 0 3 minutes read

Given an array arr[] of size N, the task is to find the frequency of each distinct element present in the given array.

Examples:

Input: arr[] = { 1, 100000000, 3, 100000000, 3 }
Output: { 1 : 1, 3 : 2, 100000000 : 2 }
Explanation:
Distinct elements of the given array are { 1, 100000000, 3 }
Frequency of 1 in the given array is 1.
Frequency of 100000000 in the given array is 2.
Frequency of 3 in the given array is 2.
Therefore, the required output is { 1 : 1, 100000000 : 2, 3 : 2 }

Input: arr[] = { 100000000, 100000000, 800000000, 100000000 }
Output: { 100000000 : 3, 800000000 : 1}

Approach: The problem can be solved using Binary search technique. Follow the steps below to solve the problem:

Sort the array in ascending order.
Traverse the array and for each distinct array element, find its lower_bound index and upper_bound indices using binary search and store in variables, say LB and UB respectively. Print the value of (UB – LB) as the frequency of that element.

Below is the implementation of the above approach:

C

// C program to implement
// the above approach
 
#include <stdio.h>
#include <stdlib.h>
 
// Comparator function to sort
// the array in ascending order
int cmp(const void* a,
        const void* b)
{
    return (*(int*)a - *(int*)b);
}
 
// Function to find the lower_bound of X
int lower_bound(int arr[], int N, int X)
{
    // Stores minimum possible
    // value of the lower_bound
    int low = 0;
 
    // Stores maximum possible
    // value of the lower_bound
    int high = N;
 
    // Calculate the upper_bound
    // of X using binary search
    while (low < high) {
 
        // Stores mid element
        // of low and high
        int mid = low + (high - low) / 2;
 
        // If X is less than
        // or equal to arr[mid]
        if (X <= arr[mid]) {
 
            // Find lower_bound in
            // the left subarray
            high = mid;
        }
 
        else {
 
            // Find lower_bound in
            // the right subarray
            low = mid + 1;
        }
    }
 
    // Return the lower_bound index
    return low;
}
 
// Function to find the upper_bound of X
int upper_bound(int arr[], int N, int X)
{
    // Stores minimum possible
    // value of the upper_bound
    int low = 0;
 
    // Stores maximum possible
    // value of the upper_bound
    int high = N;
 
    // Calculate the upper_bound
    // of X using binary search
    while (low < high) {
 
        // Stores mid element
        // of low and high
        int mid = low + (high - low) / 2;
 
        // If X is greater than
        // or equal  to arr[mid]
        if (X >= arr[mid]) {
 
            // Find upper_bound in
            // right subarray
            low = mid + 1;
        }
 
        // If X is less than arr[mid]
        else {
 
            // Find upper_bound in
            // left subarray
            high = mid;
        }
    }
 
    // Return the upper_bound index
    return low;
}
 
// Function to find the frequency
// of an element in the array
int findFreq(int arr[], int N,
             int X)
{
    // Stores upper_bound index of X
    int UB = upper_bound(arr, N, X);
 
    // Stores lower_bound index of X
    int LB = lower_bound(arr, N, X);
 
    return (UB - LB);
}
 
// Utility function to print the frequency
// of each distinct element of the array
void UtilFindFreqArr(int arr[], int N)
{
    // Sort the array in
    // ascending order
    qsort(arr, N,
          sizeof(int), cmp);
 
    // Print start bracket
    printf("{ ");
 
    // Traverse the array
    for (int i = 0; i < N;) {
 
        // Stores frequency
        // of arr[i];
        int fr = findFreq(arr, N,
                          arr[i]);
 
        // Print frequency of arr[i]
        printf("%d : %d",
               arr[i], fr);
 
        // Update i
        i++;
 
        // Remove duplicate elements
        // from the array
        while (i < N && arr[i] == arr[i - 1]) {
 
            // Update i
            i++;
        }
 
        // If arr[i] is not
        // the last array element
        if (i <= N - 1) {
 
            printf(", ");
        }
    }
 
    // Print end bracket
    printf(" }");
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 100000000, 3,
                  100000000, 3 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    UtilFindFreqArr(arr, N);
}

Output:

{ 1 : 1, 3 : 2, 100000000 : 2 }

Time Complexity: O(N * log(N))
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!