For n/2 I came across a nice algo sometime back.
here is how to do it (I am providing algo):
int A[n], i, num, freq=0;
set num = A[0] and freq= 1; // assume first number to be the >n/2 times
occurring element.
from i=1 to n-1
{
if (A[i] == num)
freq++;
else
freq--;
freq = (freq < 0)? 0: freq; // in case freq. goes negative.
if (freq == 0) // That means there might be any other element occurring
more than the current element.
num = A[i];
}
if (freq)
return num;
else
return NULL;
How does it work:
consider this array: 9 , 9 ,1 ,1 ,5 ,1 ,1 ,9 ,1 (n = 9, n/2 = 4)
- for 1 to be the answer, its freq should be 5 or more.
- now if 1 has occurred for 5 times, means 4 times some other number has
occurred (irrespective of how many times other numbers have occurred). so
the overall extra occurrence is of 1 is 1.
run the algo (i = 1 to 8):
- i = 1 , A[i] = 9, n = 9, freq = 1 => freq++;
- i = 2 , A[i] = 1, n = 9, freq = 2 => freq --;
- i = 3, A[i] = 1, n = 9, freq = 1 => freq -- and n is set to 1
continue till end and you will find that for n = 1, freq = 1;
so the answer will be 1.
please do tell me if you find some test case for which above algo fails.
Will be looking for a similar soln. for n/4.
On 15 August 2011 16:31, contiguous <priyadee...@gmail.com> wrote:
> Design an algorithm to find all elements that appear more than n/2
> times in the list. Then do it for elements that appear more than n/4
> times.
>
> --
> 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
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
___________________________________________________________________________________________________________
Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
