how is it possible in O(N) sir,wen array unordered??if u prove it u shall be then next DONALD E KNUTH
On Thu, Aug 13, 2009 at 7:26 PM, Angad Karunan <[email protected]>wrote: > 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 <[email protected]>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 <[email protected]> >> *To:* [email protected] >> *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 [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 -~----------~----~----~----~------~----~------~--~---
