[algogeeks] Re: find the most occured (more than N/2 times , where N is the length of the array) element in an array

[Siva]

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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---