Home » Data Structure

Find occurrence of each element in an array using simple method O(n^2) and hashing O(n) time

In this article, we are going to learn how to find occurrence of each element in an array using two different methods 1) simple method O(n^2) time and 2) hashing O(n) time with C programs?
Submitted by IncludeHelp, on December 08, 2017

It is the concept or logic used to make search operations faster i.e. Search an element in O(1) time. It treats the indexes of an array as the elements of another array.

Mainly it is used for the questions related to occurrence of elements of an array.

Let us understand it with the help of an example,

Given an array and we need to count of occurrence of each element.

Solution:

/*C program to find occurrence of each element in one dimensional array.*/
 
#include <stdio.h>
#define MAX 100

int main()
{
	int arr[MAX],n,i,j;
	int num,count;

	printf("Enter total number of elements: ");
	scanf("%d",&n);

	//read array elements
	printf("Enter array elements:\n");
	for(i=0;i< n;i++)
	{
		printf("Enter element %d: ",i+1);
		scanf("%d",&arr[i]);
	}

	//count occurence of each element
	for(i=0;i< n;i++)
	{
		count=0;
		for(j=0; j<n;j++)
			if(arr[i]==arr[j])
				count++;
		printf("Occurrence of %d is: %d\n",arr[i],count);
	}

	return 0;
}

Output

But in this the Time Complexity is O(n^2) and it prints the occurrence statement for an element the no. of times it appears.

So, to solve this problem and reduce the complexity to O(n), we will use the concept of hashing.

Using hashing

/*
C program to find occurrence of each element in one dimensional array.
(Using hashing) 
*/

#include <stdio.h>
#define MAX 100

int main()
{
	int arr[MAX],n,i,j;
	int num,count, hash[MAX] = {0};

	printf("Enter total number of elements: ");
	scanf("%d",&n);

	//read array elements
	printf("Enter array elements:\n");
	for(i=0;i< n;i++)
	{
		printf("Enter element %d: ",i+1);
		scanf("%d",&arr[i]);
	}


	// Using another arrays index as element
	for(i=0; i<n; i++)
		hash[arr[i]]++;

	printf("Occurence of each element:\n");
	for(i=0; i<n; i++)
	{
		if (hash[arr[i]]!=0)
			printf("%d occurs %d times\n", arr[i], hash[arr[i]]);
		hash[arr[i]] = 0;
	}

	return 0;
}

Output