Thursday, August 4, 2011

You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.

Posted by Unknown at 4:08 AM
Labels:Data

3 comments :

thoughts_anshul said...

Hash table to calculate the frequency of each number. and then scanning the whole of hash table to know the if there is a number which has freq >= N/10

August 29, 2011 at 10:13 PM
Unknown said...

@anshul yes this idea works , bus it requires O(n) space,a more space efficient approach to use Moore Voting Algorithm that doesn't requires any extra space, its used to find majority element in an array , isn't it ?

Correct me if i am wrong or any other idea you have to do it efficiently ?

Cheers !!!
Shashank

September 1, 2011 at 8:37 AM
Unknown said...

Hi I have question regarding Moore Voting Algorithm
As per algo
AAADDCCDABCCCAA I should get A as the majority however I will get C as the answer...Correct me If I am wrong

October 24, 2011 at 12:32 AM

Post a Comment

Subscribe to: Post Comments ( Atom )