Given an unsorted array of integers whose each element lies in range 0 to n-1 where n is the size of the array, calculate the frequency of all elements present in the array in linear time and using constant space.

For example,

**Input:** { 2, 3, 3, 2, 1 }

**Output:**

Element 1 appears 1 times

Element 2 appears 2 times

Element 3 appears 2 times

Simple solution is to use a count array. We traverse through the given array and update frequency of each element in count array. Finally after all array elements are processed, we iterate through the count array to print frequencies. We can also use map instead of count array but using map do not take advantage of the fact that array elements lies between 0 to n-1.

**C/C++ implementation –**

## C

#include <stdio.h>
// Function to calculate the frequency of all elements in the array void findFrequency(int A[], int n) { // create an count array of size n to store count of all array elements int freq[n];
for (int i = 0; i < n; i++) freq[i] = 0;
// update frequency of each element for (int i = 0; i < n; i++) freq[A[i]]++;
// iterate through the array to print frequencies for (int i = 0; i < n; i++) if (freq[i]) printf(“%d appears %d timesn”, i, freq[i]); }
// main function int main(void) { int A[] = { 2, 3, 3, 2, 1 }; int n = sizeof(A) / sizeof(A[0]);
findFrequency(A, n);
return 0; } |

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <unordered_map> using namespace std;
// Function to calculate the frequency of all elements in the array void findFrequency(int A[], int n) { // create an empty map to store frequency of array elements // we can also use count array of size n unordered_map<int, int> freq;
// update frequency of each element for (int i = 0; i < n; i++) freq[A[i]]++;
// iterate through the map to print frequencies for (auto it: freq) cout << it.first << ” appears “ << it.second << ” timesn”; }
// main function int main() { int A[] = { 2, 3, 3, 2, 1 }; int n = sizeof(A) / sizeof(A[0]);
findFrequency(A, n);
return 0; } |

`Output:`

Element 1 appears 1 times

Element 2 appears 2 times

Element 3 appears 2 times

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

We can also solve this problem without using any extra space by taking advantage of the fact that array elements lies in the range 0 to n-1. For each element A[i] present in the array, we increment value present at index (A[i] % n) by n. Finally, we traverse the modified array and if A[i] is more than or equal to n, then i appears in the array (A[i]/n) times.

For example, consider array {2, 3, 3, 2, 1}. After incrementing value present at index (A[i] % n) for each element A[i] by n, the array becomes {2, 8, 13, 12, 1}. Now if we take (arr[i]/n) for each index i, we get {0, 1, 2, 2, 0}. Here, A[i] denotes the frequency of index i.

**C implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <stdio.h>
// Function to calculate the frequency of all elements in the array // in linear time and without using any extra space void findFrequency(int A[], int n) { // for each element A[i], increment value present at index // (A[i] % n) by n for (int i = 0; i < n; i++) A[A[i] % n] += n;
// traverse the modified array and print their frequencies // if A[i] > n, then i appears in the array A[i]/n times for (int i = 0; i < n; i++) if (A[i]/n != 0) printf(“%d appears %d timesn”, i, A[i]/n);
// restore the array for (int i = 0; i < n; i++) A[i] = A[i] % n; }
// main function int main(void) { int A[] = { 2, 3, 3, 2, 1 }; int n = sizeof(A) / sizeof(A[0]);
findFrequency(A, n);
return 0; } |

`Output:`

1 appears 1 times

2 appears 2 times

3 appears 2 times

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Exercise:** Modify the program if array elements lies in range 1 to n

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

more link ADS

Smart Retail, Smart Agriculture, Smart supply Chain, Smart Health, Smart energy, Smart City

Blockchain, bitcoin, ethereum, blockchain technology, cryptocurrencies

Information Security, latest Hacking News, Cyber Security, Network Sec

Information Security, latest Hacking News, Cyber Security, Network Security

Blog! Development Software and Application Mobile

Development apps, Android, Ios anh Tranning IT, data center, hacking

Car News, Reviews, Pricing for New & Used Cars, car reviews and news, concept cars

Travel Blog is a unique free online travel diary for travellers across the world.