Home » Data Structure

Find occurrence of each element in an array

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

Find occurrence of each element in an array

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.

C program to find occurrence of each element in one dimensional array.

/*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.

C program to find occurrence of each element 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