Find the frequency of elements in an array using C Programming Language

Find the frequency of elements in an array using C Programming Language.

To find the frequency of elements in an array using the C programming language, you can use a hash map or an array to keep track of the frequency of each element. Here's an example implementation using an array:

Code:

#include <stdio.h>

#define SIZE 100

void findFrequency(int arr[], int size) {
int freq[SIZE] = {0}; // Initialize frequency array with zeros

// Count the frequency of each element
for (int i = 0; i < size; i++) {
freq[arr[i]]++;
}

// Print the frequency of each element
printf("Element\tFrequency\n");
for (int i = 0; i < SIZE; i++) {
if (freq[i] > 0) {
printf("%d\t%d\n", i, freq[i]);
}
}
}

int main() {
int arr[] = {2, 4, 2, 7, 8, 4, 5, 2, 1, 7, 4, 6, 3, 5};
int size = sizeof(arr) / sizeof(arr[0]);

findFrequency(arr, size);

return 0;
}

 

In this example, the findFrequency function takes an array and its size as input and uses the freq array to keep track of the frequency of each element. The main function initializes an example array arr, calculates its size, and then calls the findFrequency function to display the frequency of each element.

Keep in mind that this example assumes a maximum element value of 100 (you can adjust the SIZE macro accordingly). If you need to handle larger values, you might consider using a hash map or dynamically allocating memory for the frequency array.

 

Explanation:

#include <stdio.h>

This line includes a library that lets us use functions like printf and scanf for input and output.

#define SIZE 100

We define a constant named SIZE and set it to 100. This constant will be used to determine the maximum size of the frequency array.

void findFrequency(int arr[], int size) {

Here, we're starting the definition of a function named findFrequency. This function takes two parameters: an array arr and an integer size.

int freq[SIZE] = {0};

We declare an integer array called freq of size SIZE and initialize all its elements to 0. This array will be used to store the frequency (count) of each element in the input array.

for (int i = 0; i < size; i++) {
freq[arr[i]]++;
}

This is a loop that goes through each element in the input array (arr). For each element, it uses that element's value as an index in the freq array and increments the value stored at that index. This effectively counts how many times each element appears in the input array.

printf("Element\tFrequency\n");

This line prints a header for the output table that will show the element and its corresponding frequency.

for (int i = 0; i < SIZE; i++) {
if (freq[i] > 0) {
printf("%d\t%d\n", i, freq[i]);
}
}

This loop iterates through the freq array. If the frequency of the element at index i is greater than 0 (meaning it appeared at least once in the input array), it prints the element's value and its frequency.

}

This curly brace marks the end of the findFrequency function.

int main() {

This is the beginning of the main function, which is the entry point of the program.

int arr[] = {2, 4, 2, 7, 8, 4, 5, 2, 1, 7, 4, 6, 3, 5};

Here, we're creating an example array arr with some numbers. This array contains the data for which we want to find the frequency of elements.

int size = sizeof(arr) / sizeof(arr[0]);

This calculates the number of elements in the array arr by dividing the total size of the array by the size of a single element. It gives us the count of elements in the array.

findFrequency(arr, size);

This line calls the findFrequency function with our example array arr and its size. It will calculate and print the frequency of elements in the array.

return 0;
}

This statement signals the end of the main function and the end of the program. It tells the operating system that the program completed successfully.

 

Algorithm:

1. Include the necessary library:

   • Include the <stdio.h> library for input and output functions.

2. Define a constant:

   • Define a constant named SIZE with a value of 100.

3. Define the findFrequency function:

   • This function takes an integer array arr and an integer size as parameters.

   • Declare an integer array freq of size SIZE and initialize all elements to 0.

   • Loop through each element of the input array arr from index 0 to size - 1.

     • Use the value of arr[i] as an index in the freq array and increment the value at that index.

   • Print a header for the frequency table.

4. Loop to print frequency:

   • Loop through each index i from 0 to SIZE - 1 in the freq array.

     • If the frequency at index i is greater than 0, print the element value (i) and its corresponding frequency.

5. Define the main function:

   • Start the main function.

   • Create an integer array arr with example data.

   • Calculate the size of the array using sizeof(arr) / sizeof(arr[0]).

   • Call the findFrequency function with the arr array and its size.

6. Return from main:

   • Return 0 to indicate successful program execution.

Here's the pseudocode representation of the algorithm:

INCLUDE library <stdio.h>

DEFINE constant SIZE = 100

DEFINE FUNCTION findFrequency(arr[], size)
DECLARE freq[SIZE] and initialize all elements to 0

FOR i = 0 TO size - 1
freq[arr[i]] = freq[arr[i]] + 1

PRINT "Element\tFrequency"

FOR i = 0 TO SIZE - 1
IF freq[i] > 0
PRINT i, freq[i]

DEFINE FUNCTION main
START main function
DECLARE arr with example data
CALCULATE size of arr
CALL findFrequency(arr, size)
RETURN 0

CALL main function

This pseudocode represents the step-by-step logic of the program without the specifics of C syntax.

 

Time Complexity:

Let's analyze the time complexity of the above program step by step:

1. Initializing freq array: This step takes constant time since it involves initializing an array of fixed size SIZE (100 in this case). So, it's O(1).

2. Loop for calculating frequency: In this loop, you iterate over each element of the input array exactly once. The loop runs size times, where size is the number of elements in the input array.

3. Loop for printing frequencies: In this loop, you iterate over the freq array of fixed size SIZE (100 in this case) and print elements that have a frequency greater than 0.

The dominant factor that contributes to the time complexity is the loop that calculates the frequency of elements, as it iterates through each element in the input array.

Therefore, the time complexity of the program is O(size), where size is the number of elements in the input array. In the worst case, the algorithm's performance will grow linearly with the size of the input array.

 

Space Complexity:

The space complexity of the program is determined by the additional memory space required by the program to execute. Let's break down the space usage step by step:

1. arr Array: The memory space required for the arr array is proportional to the number of elements in the array. So, it's O(size), where size is the number of elements in the input array.

2. freq Array: The memory space required for the freq array is fixed and depends on the constant SIZE. It's O(SIZE), which simplifies to O(1) since it's a constant size array.

3. Loop Variables and Other Variables: The space required for loop variables and other temporary variables is negligible compared to the size of the arrays. These variables occupy constant space, so they contribute O(1) space.

Overall, the dominant factor in space complexity is the memory required for the arr array (O(size)) and the freq array (O(1)). Therefore, the space complexity of the program is O(size), where size is the number of elements in the input array.

Thank You