CareerCup

perform counting sort and create an integer array of length 50.
that would surely do the job..

I am not really sure why sorting is necessary at all since all we have to do is find out the frequency of each number in the array.

I would go for hashing the array where the key=number and value=frequency of number.
Hashing and printing the values would take n+n time=O(n) time and also due to the hash table O(n) space complexity

counting sort is not really "sort". it is like bucket sort. put every item into propertied bucket. in this case, increment the item whose index is indicated by value of the item.
int[] arr = int[50];
for(int i:arrlist){
arr[i]++;
}

counting sort is not really "sort". it is like bucket sort. put every item into propertied bucket. in this case, increment the item whose index is indicated by value of the item.
int[] arr = int[50];
for(int i:arrlist){
arr[i]++;
}

What saumil suggests is using the counts from the counting sort stage. since the range 1-50 is known we can store in a array the counts.

Hash approach sugested by someone else is exactly the same but it is typically better to use an array if the range is known. Think of a Array as the Perfect hash.

What saumil suggests is using the counts from the counting sort stage. since the range 1-50 is known we can store in a array the counts.

Hash approach sugested by someone else is exactly the same but it is typically better to use an array if the range is known. Think of a Array as the Perfect hash.

How abt this approach??

for(int i = 0 ; i < n ; i++){
a[a[i]] = a[i]+(a[a[i]]%a[i]);
}

for(int i = 0 ; i < 50 ; i++){
cout << "no of occurances of" << i << ": ";
int occur = a[i]/i;
if(a[i]%i == 0)
occur--;
cout << occur << endl;
}

correct if this is inefficient