Frequencies of Limited Range Array Elements
Given an array A[] of N positive integers which can contain integers from 1 to N where elements can be repeated or can be absent from the array. Your task is to count the frequency of all elements from 1 to N.
Example:-
Input:
N = 5
A[] = {2,3,2,3,5}
Output: 0 2 2 0 1
Explanation:
Counting frequencies of each array element
We have:
1 occurring 0 times.
2 occurring 2 times.
3 occurring 2 times.
4 occurring 0 times.
5 occurring 1 time.
we need to solve this question in O(n) time and O(1) space, so that's why we can’t use a hashmap because it takes O(n) space. So here we have one important clue from the question that our value in the range of 1 to N. But here I have an issue if I can use that value with reference to the index I don't have Nth index so first I will subtract 1 from each of element of the array. So array {2,3,2,3,5} becomes {1,2,1,3,4}. Now we know that each of the array elements in the range of 0 to N-1. can you get some hint here?
See we can get value at each index by arr[i]%N. You get an idea of why we use %N why not only arr[i].
You will get that idea also after reading the below text.
Let get original value at index ( i ) is arr[i]%N and we also know that arr[i]%N will not increase than N-1 and not less than 0. So we go at index arr[i]%N and add N to the current value. so for array {1,2,1,3,4}, initially we get current value 1, at index 1 we add N to current value of index 1 so it becomes 2+5 = 7. The modified array will be {1,7,1,3,4}. Now we will consider second element 7 how we get the original value of at index 1 we get this by arr[1]%N=7%5=2. So you get an idea now why we are doing %N. at index 2 increase by 5, 1+5 =6. so this happens for each element and our final array will look like this {1,12,11,8,4}. We are almost done.
Now we see that at each index how many times N is added. How we get this for index i. we get this by arr[i]/N which is the frequency of (i+1) element in the array. so for our array frequency will be like this {0,2,2,1,0} so frequency of 1 is 0, for 2 is 2, for 3 is 2, for 4 is 1, for 5 is 0. which is true for our array so now you get all idea.
Here is pseudo-code:
//to get element in range of 0 to (n-1)
for(int i=0;i<n;i++){
arr[i] — ;
}
for(int i=0;i<n;i++){
arr[arr[i]%n] = arr[arr[i]%n] + n;
}
//check how many times n add at index i
for(int i=0;i<n;i++){
arr[i] = arr[i]/n;
}
Thanks for reading!!.