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:
#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.
#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.
Include the necessary library:
Include the <stdio.h>
library for input and output functions.
Define a constant:
Define a constant named SIZE
with a value of 100.
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.
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.
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.
Return from main
:
Return 0 to indicate successful program execution.
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.
Let's analyze the time complexity of the above program step by step:
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).
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.
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.
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:
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.
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.
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.