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

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++

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 –

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