Author |
Topic: Finding the decimal dominant in linear time (Read 5458 times) |
|
Dufus
Newbie
Posts: 43
|
 |
Finding the decimal dominant in linear time
« on: Jul 24th, 2009, 12:16am » |
 Quote  Modify
|
I recently encountered this interesting problem at
http://www.cse.iitd.ernet.in/~sbaswana/Puzzles/Algo/algo.html
I couldnt find a similar existing problem.
Perhaps it is related to majority element problem (finding element with more than n/2 occurences in an array of n elements)
Problem:-
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Finding the decimal dominant in linear t
« Reply #1 on: Jul 24th, 2009, 1:38am » |
Quote Modify
|
You can solve it in a similar way to the majority element problem
Use 9 collection bins for different elements. If they all contain an element, and a new element is different from the ones being collected, remove one from each bin. In the end you have 9 candidates that might occur more than n/10 times. Count them by going through the array a second time.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: Finding the decimal dominant in linear t
« Reply #2 on: Jul 24th, 2009, 2:28am » |
Quote Modify
|
on Jul 24th, 2009, 1:38am, towr wrote:You can solve it in a similar way to the majority element problem
Use 9 collection bins for different elements. If they all contain an element, and a new element is different from the ones being collected, remove one from each bin. In the end you have 9 candidates that might occur more than n/10 times. Count them by going through the array a second time. |
|
Thanks Towr but could you please elaborate a little bit more.
I think they way u have solved this problem can be generalized for any constant k.
In this case k = 10.
So, lets consider the sample input with n = 10, k = 3 :-
1,1,1,2,2,2,3,3,3,3 (input may be unsorted)
Then I suppose I would need k-1 = 3-1 = 2 bins say A1 and A2.
Now how am I supposed to proceed further?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding the decimal dominant in linear t
« Reply #3 on: Jul 24th, 2009, 3:10am » |
Quote Modify
|
on Jul 24th, 2009, 2:28am, Dufus wrote:
So, lets consider the sample input with n = 10, k = 3 :-
1,1,1,2,2,2,3,3,3,3 (input may be unsorted)
Then I suppose I would need k-1 = 3-1 = 2 bins say A1 and A2.
Now how am I supposed to proceed further? |
|
1,1,1,2,2,2,3,3,3,3 A1={}, A2={}
>>
1,1,2,2,2,3,3,3,3 A1={1}, A2={}
>>
1,2,2,2,3,3,3,3 A1={1,1}, A2={} (You could just use a counter, but I'll just add the elements as in a list instead)
>>
2,2,2,3,3,3,3 A1={1,1,1}, A2={}
>>
2,2,2,3,3,3,3 A1={1,1,1}, A2={2}
>>
2,3,3,3,3 A1={1,1,1}, A2={2,2}
>>
3,3,3,3 A1={1,1,1}, A2={2,2,2}
>>
3,3,3 A1={1,1}, A2={2,2} (3 is different from 1 and 2, so deleted an element from both bins)
>>
3,3 A1={1}, A2={2}
>>
3 A1={}, A2={}
>>
_ A1={3}, A2={}
The only non-empty bin contains a 3, so now we run through the list of numbers again, counting the number of 3s, of which there are four. 4 >10/3, so we can output 3 as the only element that occurs more than n/3 times.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sree37
Newbie
Posts: 1
|
|
Re: Finding the decimal dominant in linear t
« Reply #4 on: Dec 29th, 2011, 8:28am » |
Quote Modify
|
Sorry for reopening this post again
@towr, Could you please explain the time and space complexity?
I believe the expected answer is O(N) time with constant space complexity.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding the decimal dominant in linear t
« Reply #5 on: Dec 29th, 2011, 9:48am » |
Quote Modify
|
Yes. If you use counters (instead of lists), then space would be constant (9 counters); and you pass through the array twice incrementing one of the counters each time, so it takes O(N) time to get the final answer.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print