Here is a modified function that finds the element that crosses a particular
percentage in an array. Please note that the code returns a false value if
there is no number that appears more frequently than the input percentage.
Loop through the array in O(n) and ensure that num indeed is an acceptable
answer.
int getNumCrossingPercentage ( Array arr, int percentage) {
int carrot = percentage; // Positive marks for the
current number if it matches the current candidate maxfreq number
int stick = 100 - percentage; // Negative marks if it doesn't
match the maxFreq number
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 += carrot;
else
freq -= stick;
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 NULL;
//TODO: Loop through the array again and check if num indeed does appear in
the input percentage.
// and only then return num, else return NULL again.
if (freq)
return num;
else
return NULL;
}
On Mon, Aug 15, 2011 at 7:21 PM, Dipankar Patro <[email protected]> wrote:
> 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 <[email protected]> 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 [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?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 [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?hl=en.
>
--
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?hl=en.
