@Pramod Nice work. Although I think Carrot = 100 - percentage and Stick =
percentage will work instead of the current values.
On Tue, Aug 16, 2011 at 1:13 AM, PramodP <p.pramod.n...@gmail.com> wrote:
> 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 <dip10c...@gmail.com>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 <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.
>>
>
> --
> 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.
>
--
Atul Purohit
--
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.
