interesting discussion going on the question, check this link-- http://stackoverflow.com/questions/9442958/find-the-element-occurring-b-times-in-an-an-array-of-size-nkb
-- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> On Fri, Feb 17, 2012 at 12:25 PM, atul anand <atul.87fri...@gmail.com>wrote: > @Siddhartha : doing bitwise addtiton may result into overflow if values > are large..... > correct me if i am wrong. > > On Fri, Feb 17, 2012 at 10:04 AM, Siddhartha Banerjee < > thefourrup...@gmail.com> wrote: > >> convert the numbers into base k... and do bitwise addition of numbers, >> where >> bit(a)+bit(b)=bit(a+b)mod(k) >> of you convert all the numbers into base k and add them bitwise in a >> variable say x, then the numbers occuring nk times vanish, and the final >> result stored in x is a+a+....+a(b times) where a is the number repeating b >> times... >> next time go through the array again and see whether any number when >> added with itself b times gives the same result as x, if yes, out put that >> number. >> >> I had seen a solution to a problem where in an array of size 3n+1, each >> element except one repeating thrice, we need to find the non repeating >> element in O(n) time O(1) space, i tried to generalize the proof to fit >> this case... >> >> -- >> 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. > -- 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.
