Find the the occurrence of each number from given array of size n , where elements ranges from 0 to n-1 ?
Complexity : O(n)
Space complexity : O(1)
e.g.
Input:
5 3 3 2 1 3 8 7 3
Output:
3 occurs 4 times
Solution :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<stdio.h> #include<math.h> void No_of_Occurrence(int A[],int length){ int i=0,temp; while(i<=length-1){ if(A[i]>=0){ if(A[A[i]]>=0){temp=A[i];A[i]=A[A[i]];A[temp]=-1;} else{A[A[i]]--;A[i]=-length;i++;} } else i++; } for(i=0;i<=length-1;i++){ if(A[i]>-length){printf("%d occurred %d times\n",i,abs(A[i]));} } } int main(){ int i=0,temp;int A[]={2,5,0,5,2,2,5,5,0}; int length=9; No_of_Occurrence(A,length); return 0; } |
Code provided by : Arpit Agrawal