why do you have to sort or do anything more if only one element repeats itself? just reading the array once shall give you the answer in O(n) time... so i guess there must be a solution better than O(n) time as the element repeats in a particular fashion. but cant think of anythin :P
On Tue, Aug 11, 2009 at 11:51 PM, manish bhatia <mb_mani...@yahoo.com>wrote: > Well instead of using extra memory, we can in-place sort the arraay in > O(nlog(n)) and then do an iteration (O(n)) to find out the repeated number. > But the catch is that number is repeated 2^i times. That is the hint we > should use > > ------------------------------ > *From:* ankur aggarwal <ankur.mast....@gmail.com> > *To:* algogeeks@googlegroups.com > *Sent:* Sunday, 9 August, 2009 5:47:32 PM > *Subject:* [algogeeks] Re: Finding repeated element in most efficient way > > > @richa.. > ques is in complete i think . > there shud be some conditions given .. > > otherwise > hash them > but lots of space will b wasted.. > > > or sort them > > try to put the conditions.. > > > > ------------------------------ > See the Web's breaking stories, chosen by people like you. Check out Yahoo! > Buzz <http://in.rd.yahoo..com/tagline_buzz_1/*http://in.buzz.yahoo.com/>. > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---