each number except one is there only once, and one number that repeats can repeat power of two times. 2,4,8,16.
the best solution is to use trie, it is linear in number of bits of input. But It is interresting if there is solution using unit cost arithmetics. Or by using randomized algorithm, and pick prime number of enough size, like n^2,do the right stuff and, it can be done with low cost with high probability. 2009/8/17 umesh kewat <[email protected]> > Any Body can tell me what is the exact problem? because i m reading this > thread 1st time over here. whether u wanna one repeated element in array or > all set of all repeated element in given array. i have some solution with > single traversal without using extra space but they depend on constraint so > please give the detailed problem. > > On Mon, Aug 17, 2009 at 5:32 AM, Shyam <[email protected]>wrote: > >> >> I think I could do it in O(n) . >> >> var bits=0 >> var @array >> >> for each i in array >> if (bits & i)!=0 >> return i >> else >> bits=bits | i; >> end if >> end for >> >> I just use the pattern for powers of two >> >> let array be 2,4,2 >> >> so first >> bits=0 i=2 so bits(000) & i(010) is 0 so bits= bits | i which is >> bits=010 >> next >> bits=2 i=4 so bits(010) & i(100) is 0 so bits= bits | i which is >> bits=110 >> next >> bits=6 i=2 so bits(110) & i(010) is 2 which is !=0 so we return i. >> >> I think that should be it. >> >> >> > > > -- > Thanks & Regards > > Umesh kewat > 09966796569 > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
