Given an array arr[] of size N, the task is to find the frequency of each distinct element present in the given array.
Examples:
Input: arr[] = { 1, 100000000, 3, 100000000, 3 }
Output: { 1 : 1, 3 : 2, 100000000 : 2 }
Explanation:
Distinct elements of the given array are { 1, 100000000, 3 }
Frequency of 1 in the given array is 1.
Frequency of 100000000 in the given array is 2.
Frequency of 3 in the given array is 2.
Therefore, the required output is { 1 : 1, 100000000 : 2, 3 : 2 }Input: arr[] = { 100000000, 100000000, 800000000, 100000000 }
Output: { 100000000 : 3, 800000000 : 1}
Approach: The problem can be solved using Binary search technique. Follow the steps below to solve the problem:
- Sort the array in ascending order.
- Traverse the array and for each distinct array element, find its lower_bound index and upper_bound indices using binary search and store in variables, say LB and UB respectively. Print the value of (UB – LB) as the frequency of that element.
Below is the implementation of the above approach:
C
// C program to implement// the above approach#include <stdio.h>#include <stdlib.h>// Comparator function to sort// the array in ascending orderint cmp(const void* a, const void* b){ return (*(int*)a - *(int*)b);}// Function to find the lower_bound of Xint lower_bound(int arr[], int N, int X){ // Stores minimum possible // value of the lower_bound int low = 0; // Stores maximum possible // value of the lower_bound int high = N; // Calculate the upper_bound // of X using binary search while (low < high) { // Stores mid element // of low and high int mid = low + (high - low) / 2; // If X is less than // or equal to arr[mid] if (X <= arr[mid]) { // Find lower_bound in // the left subarray high = mid; } else { // Find lower_bound in // the right subarray low = mid + 1; } } // Return the lower_bound index return low;}// Function to find the upper_bound of Xint upper_bound(int arr[], int N, int X){ // Stores minimum possible // value of the upper_bound int low = 0; // Stores maximum possible // value of the upper_bound int high = N; // Calculate the upper_bound // of X using binary search while (low < high) { // Stores mid element // of low and high int mid = low + (high - low) / 2; // If X is greater than // or equal to arr[mid] if (X >= arr[mid]) { // Find upper_bound in // right subarray low = mid + 1; } // If X is less than arr[mid] else { // Find upper_bound in // left subarray high = mid; } } // Return the upper_bound index return low;}// Function to find the frequency// of an element in the arrayint findFreq(int arr[], int N, int X){ // Stores upper_bound index of X int UB = upper_bound(arr, N, X); // Stores lower_bound index of X int LB = lower_bound(arr, N, X); return (UB - LB);}// Utility function to print the frequency// of each distinct element of the arrayvoid UtilFindFreqArr(int arr[], int N){ // Sort the array in // ascending order qsort(arr, N, sizeof(int), cmp); // Print start bracket printf("{ "); // Traverse the array for (int i = 0; i < N;) { // Stores frequency // of arr[i]; int fr = findFreq(arr, N, arr[i]); // Print frequency of arr[i] printf("%d : %d", arr[i], fr); // Update i i++; // Remove duplicate elements // from the array while (i < N && arr[i] == arr[i - 1]) { // Update i i++; } // If arr[i] is not // the last array element if (i <= N - 1) { printf(", "); } } // Print end bracket printf(" }");}// Driver Codeint main(){ int arr[] = { 1, 100000000, 3, 100000000, 3 }; int N = sizeof(arr) / sizeof(arr[0]); UtilFindFreqArr(arr, N);} |
{ 1 : 1, 3 : 2, 100000000 : 2 }
Time Complexity: O(N * log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
