tag:blogger.com,1999:blog-6314876008291942531.post3280943561916964349..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Given a stream find the element which appears the majority of timesUnknownnoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6314876008291942531.post-13508645105130066332010-04-23T20:51:14.566-07:002010-04-23T20:51:14.566-07:002 clarifications
1. Are you allowed to store the n...2 clarifications<br />1. Are you allowed to store the numbers ? ( I assume not, else the problem is trivial)<br />2. If your answer to 1 (above) is "no", then do you want a deterministic or probable answer ?<br /><br />I found a nice resource on <b>Stream Algorithms</b>, will have to dig into it then :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-29493590910806116822010-04-17T00:42:39.731-07:002010-04-17T00:42:39.731-07:00Assume the stream of integers is appearing in arra...Assume the stream of integers is appearing in array 'a'.<br />Initialize - <br />majority = a[0];<br />counter = 1;<br /><br />As the number comes in (i=1 onwards) -<br />if a[i] == majority -> counter++;<br />else if counter == 0 -> majority = a[i];<br />else counter--;<br /><br />At the end, if there is majority, it is saved in the variable majority.<br /><br />P.S.: I commented earlier also. But it is now appearing the other post "Server allocation...." Please delete from there.Anonymoushttps://www.blogger.com/profile/03337365075523724707noreply@blogger.com