Checking whether an array contains a majority elemnt....

[Amit Bhatnagar]

An array has a majority element if there exists an element whose
frequency is more than (N/2 +1 ) where N is the number of elemnts in
array..
We need to write a program to find the majority elemnt if it exists..

 

[Amit Bhatnagar]

An array has a majority element if there exists an element whose
frequency is more than (N/2 +1 ) where N is the number of elemnts in
array..
We need to write a program to find the majority elemnt if it exists..

One approach I was able to think of was to sort the array using some
gud sorting algo (may be Quicksort).. This way we can be sure that the
only contender for the majority elemnt is the num at position ( N/2 +1)
Now we can just count the frequency of this elemnt ion a single pass
and see whether it's majority element or not...


But can we have a better soln that works in O(n) time without using an
auxillary array??

 

[Vladimir Oka]

Amit Bhatnagar opined:

One approach I was able to think of was to sort the array using some
gud sorting algo (may be Quicksort).. This way we can be sure that
the only contender for the majority elemnt is the num at position (
N/2 +1) Now we can just count the frequency of this elemnt ion a
single pass and see whether it's majority element or not...


But can we have a better soln that works in O(n) time without using
an auxillary array??

This is better asked in comp.programming (being an algorithm, rather
than C question).

Once you decide on the algorithm and get stuck implementing it in C, do
come back here and ask.

 

[Eric Sosman]

An array has a majority element if there exists an element whose
frequency is more than (N/2 +1 ) where N is the number of elemnts in
array..
We need to write a program to find the majority elemnt if it exists..

See Vladimir Oka's response. Also, re-examine your
definition of "majority array," because I think you'll
find that it's unsatisfactory. For example, the array
of two elements { 42, 42 } would not meet the definition
as stated, nor would the three-element array { 42, 42, 0 }.

 

[osmium]

An array has a majority element if there exists an element whose
frequency is more than (N/2 +1 ) where N is the number of elemnts in
array..
We need to write a program to find the majority elemnt if it exists..

That seems like a very badly formed question, at least in English. *The*
majority element is not the same as *an* majority element. If there is a
cute answer it is probably in one of the two _Programming Pearls_ books by
Bentley. There is nothing above that indicates anyone should do anything
other than simply write a program to do whatever it is that needs to be
done.

 

[googmeister]

An array has a majority element if there exists an element whose
frequency is more than (N/2 +1 ) where N is the number of elemnts in
array..
We need to write a program to find the majority elemnt if it exists..

You can solve this problem with sorting or hashing, but there is
also a simple O(N) algorithm that your prof is expecting.

 

[Walter Roberson]

"Amit Bhatnagar" writes:

That seems like a very badly formed question, at least in English. *The*
majority element is not the same as *an* majority element.

How could you have two distinct elements, each of which occured in more
than half of the positions of the array? By the definition given above,
the minimum possible frequency for the two hypothetical items together
would be 2*(N/2+1) which would be N+2 slots out of an array that has
only N slots.

Thus, given the definition above, an array either has no majority
elements, or it has exactly one majority element.

[Presuming here that an 'element' of an array is a value stored in the
array.]

 

[gw7rib]

You can solve this problem with sorting or hashing, but there is
also a simple O(N) algorithm that your prof is expecting.

I'm intrigued! While I'd like to try and work it out myself (ie no big
hints yet, please) I'd be grateful if you could answer a few questions
as to this algorithm you're thinking of:

1) Will it work if you define "majority element" to be one that occurs
more than N/2 times (ie the normal definition) or does it need the OP's
more restricted definition?

2) Is it O(1) in terms of store? My first idea (which I think won't
work anyway) involved a recursive function and so used up more store as
N increased, even though the function only had a fixed number of
variables.

3) Is it a "computery" solution? Eg not mathematical, no powers of
primes or the like?

Thanks for any help! I'll see if I can crack it...

 

[kar1107]

I'm intrigued! While I'd like to try and work it out myself (ie no big
hints yet, please) I'd be grateful if you could answer a few questions
as to this algorithm you're thinking of:

1) Will it work if you define "majority element" to be one that occurs
more than N/2 times (ie the normal definition) or does it need the OP's
more restricted definition?

2) Is it O(1) in terms of store? My first idea (which I think won't
work anyway) involved a recursive function and so used up more store as
N increased, even though the function only had a fixed number of
variables.

3) Is it a "computery" solution? Eg not mathematical, no powers of
primes or the like?

Thanks for any help! I'll see if I can crack it...

As others have pointed, this is not a C question; but an algorithm one.
Good luck having fun in cracking it. Yes, there is an O(N) time and
O(1) space algorithm for it. Pretty neat one ..sorry I cheated and used
google to get to it.

Karthik

 

[googmeister]

I'm intrigued! While I'd like to try and work it out myself (ie no big
hints yet, please) I'd be grateful if you could answer a few questions
as to this algorithm you're thinking of:

1) Will it work if you define "majority element" to be one that occurs
more than N/2 times (ie the normal definition) or does it need the OP's
more restricted definition?

It works for either.

2) Is it O(1) in terms of store? My first idea (which I think won't
work anyway) involved a recursive function and so used up more store as
N increased, even though the function only had a fixed number of
variables.

Yes, it can be done in-place - O(1) extra space.

3) Is it a "computery" solution? Eg not mathematical, no powers of
primes or the like?

No fancy math, just a nice pleasing aha at the end.

Thanks for any help! I'll see if I can crack it...

Enjoy.