Hi,
Here is the O(n) solution for this problem-
int findArrayHas(int *a, int n)
{
int c=0;
int i;
int x;
for(i=0;i<n;i++)
{
if(c==0)
{
c=1;
x=a[i];
}
else
{
if(a[i]!=x)
c--;
else
c++;
}
}
//printf("\n%d",c);
return x;
}
int main()
{
int a[7]={2,3,3,2,3,2,2};
int i,c,cnt=0;
c=findArrayHas(a,7);
//check if val appears more than n/2 times with an array traversal
for(i=0;i<7;i++)
{
if(a[i]==c)
cnt++;
}
if(cnt>7/2)
printf("\nArray has %d repeated %d times",c,cnt);
else
printf("\n No element repeats more than n/2 times");
return 0;
}
Cheers
Siva
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
