Count The Frequency Of Each Element Of An Array In C

Counting the frequency of each element in an array is a fundamental task in programming that involves determining how many times each unique element appears. This operation is crucial for data analysis, statistical computations, and various algorithmic challenges. In this article, you will learn how to implement different approaches in C to efficiently count element frequencies within an array.

Problem Statement

The core problem is to iterate through an array of numbers and identify each unique element, subsequently calculating how many times each of these unique elements occurs within the array. For instance, given an array [10, 20, 20, 10, 10, 30, 40, 30], the goal is to output that 10 appears 3 times, 20 appears 2 times, 30 appears 2 times, and 40 appears 1 time. This task is essential in scenarios requiring data distribution insights, anomaly detection, or optimizing data structures.

Example

Consider the integer array arr = [1, 2, 8, 3, 2, 2, 2, 5, 1]. The expected output for element frequencies would be:

• Element 1 appears 2 times.
• Element 2 appears 4 times.
• Element 3 appears 1 time.
• Element 5 appears 1 time.
• Element 8 appears 1 time.

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, readers should have a basic understanding of:

• C programming fundamentals: Variables, data types, and basic input/output.
• Arrays: Declaring, initializing, and accessing elements.
• Loops: for loops for iteration.
• Conditional statements: if-else for logic control.

No specific setup is required beyond a C compiler (like GCC).

Use Cases

Counting element frequencies is a versatile operation applied in numerous domains:

• Data Analysis: Determining the most common items in a dataset, like top-selling products in an e-commerce inventory.
• Algorithm Optimization: Identifying repeated patterns or elements to optimize search or sorting algorithms.
• Statistical Computations: Calculating modes or distribution of values in survey responses.
• Security: Analyzing frequency of character occurrences in a password for strength assessment.
• Game Development: Tracking the number of specific items collected by a player or enemies defeated.

Solution Approaches

We will explore two common approaches to count the frequency of elements in a C array.

Approach 1: Using a Separate Frequency Array with a Visited Marker

This approach involves using an auxiliary array to store the frequencies. To avoid counting the same element multiple times, a marker (like -1) is used to signify that an element has already been processed.

One-line summary: Iterate through the array, counting occurrences for each element and marking counted elements as visited.

// Count Frequency with Visited Marker
#include <stdio.h>

int main() {
    // Step 1: Initialize the array and its size
    int arr[] = {1, 2, 8, 3, 2, 2, 2, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Declare a frequency array of the same size, initialized to 0
    int freq[n];
    for (int i = 0; i < n; i++) {
        freq[i] = 0;
    }

    // Step 3: Iterate through the array to count frequencies
    for (int i = 0; i < n; i++) {
        int count = 1; // Start count for the current element

        // If the element hasn't been counted yet
        if (arr[i] != -1) {
            // Compare it with subsequent elements
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                    freq[j] = -1; // Mark element as visited by setting its freq to -1
                }
            }
            freq[i] = count; // Store the frequency of the current element
        }
    }

    // Step 4: Print the frequencies of unique elements
    printf("Element | Frequency\\n");
    printf("--------|-----------\\n");
    for (int i = 0; i < n; i++) {
        if (freq[i] != -1) { // Only print if the element was not a duplicate
            printf("%7d | %9d\\n", arr[i], freq[i]);
        }
    }

    return 0;
}

Run

Sample output:

Element | Frequency
--------|-----------
      1 |         2
      2 |         4
      8 |         1
      3 |         1
      5 |         1

Stepwise explanation:

1. Initialization: An input array arr and an auxiliary freq array of the same size are declared. freq is initialized to all zeros. The size n of the array is calculated.
2. Outer Loop: The first for loop iterates through each element of the arr.
3. Check Visited: Inside the outer loop, an if (arr[i] != -1) check ensures that elements already counted (and marked with -1 in the original array's corresponding freq index) are skipped.
4. Inner Loop: For each unvisited element arr[i], an inner for loop iterates from i + 1 to the end of the array.
5. Counting and Marking: If arr[i] matches arr[j], the count is incremented, and freq[j] is set to -1. This -1 acts as a marker to indicate that arr[j] has been counted as part of arr[i]'s frequency and should not be processed independently later.
6. Store Frequency: After the inner loop completes, the total count for arr[i] is stored in freq[i].
7. Print Results: Finally, another loop iterates through the freq array. If freq[i] is not -1 (meaning arr[i] was a unique element or the first occurrence of a repeated element), its frequency is printed alongside the element itself.

Approach 2: Using a Direct Mapping Frequency Array (for limited range elements)

This approach is highly efficient when the elements in the array are non-negative and fall within a known, relatively small range. It uses a frequency array whose indices directly correspond to the values of the elements.

One-line summary: Create a frequency array large enough to cover the maximum possible element value, then increment the count at the index corresponding to each element's value.

// Count Frequency with Direct Mapping
#include <stdio.h>

// Assuming max element value is less than 100 for this example.
// For larger ranges, dynamically allocate or adjust MAX_VALUE.
#define MAX_VALUE 100 

int main() {
    // Step 1: Initialize the array and its size
    int arr[] = {10, 20, 20, 10, 10, 30, 40, 30, 5, 20, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Declare and initialize the frequency array
    // Its size should be MAX_VALUE + 1 to accommodate elements up to MAX_VALUE
    int freq[MAX_VALUE] = {0}; // All elements initialized to 0

    // Step 3: Iterate through the input array and increment counts
    for (int i = 0; i < n; i++) {
        // Check if element is within the valid range
        if (arr[i] >= 0 && arr[i] < MAX_VALUE) {
            freq[arr[i]]++; // Increment count for the element's value
        } else {
            printf("Warning: Element %d out of defined range [0, %d).\\n", arr[i], MAX_VALUE);
        }
    }

    // Step 4: Print the frequencies of elements that appeared
    printf("Element | Frequency\\n");
    printf("--------|-----------\\n");
    for (int i = 0; i < MAX_VALUE; i++) {
        if (freq[i] > 0) { // Only print if the element appeared at least once
            printf("%7d | %9d\\n", i, freq[i]);
        }
    }

    return 0;
}

Run

Sample output:

Element | Frequency
--------|-----------
      5 |         2
     10 |         3
     20 |         3
     30 |         2
     40 |         1

Stepwise explanation:

1. Define Max Value: A MAXVALUE macro is defined to set the upper limit for element values. This determines the size of our direct-mapping frequency array.
2. Initialization: An input array arr is declared. A freq array of size MAXVALUE is declared and all its elements are initialized to 0. Each index i in freq will represent the element i from the input array.
3. Counting Frequencies: The first for loop iterates through each element arr[i] of the input array.
4. Direct Mapping: For each arr[i], its value is used directly as an index into the freq array: freq[arr[i]]++. This efficiently increments the count for that specific element. A check is included to ensure elements are within the defined range.
5. Print Results: The second for loop iterates from 0 to MAX_VALUE - 1. If freq[i] is greater than 0, it means the element i appeared in the input array, and its frequency (freq[i]) is printed.

Conclusion

Counting element frequencies in an array is a common requirement in various programming tasks. We explored two distinct approaches in C: one utilizing a visited marker for general integer arrays, and another leveraging direct mapping for arrays with elements within a limited, non-negative range. The direct mapping method offers superior performance for suitable datasets, while the visited marker approach provides a robust solution for more diverse integer inputs. Choosing the right approach depends on the characteristics and constraints of your data.

Summary

• Problem: Determine the occurrences of each unique element in an array.
• Approach 1 (Visited Marker):
• Suitable for general integer arrays.
• Uses an auxiliary array to store counts and marks elements as "visited" to prevent re-counting.
• Time complexity is generally O(N^2).
• Approach 2 (Direct Mapping):
• Highly efficient for non-negative integers within a known, limited range.
• Uses element values as indices in a frequency array to directly increment counts.
• Time complexity is O(N + M) where N is array size and M is the max element value, often simplified to O(N) if M is proportional to N or small.
• Choice: Select the method based on the range and nature of elements in your array for optimal performance.