Yes. It can be done in O(n). But you will need extra memory.The approach is similiar to what siddharth told.
Keep and array 'arr' initialised to zero. set arr[input[i]]++ for all i. At last check if any element of arr is greater than 1. Here, the memory used is a concern. Also the hint(repeated no repeats in powers of two) is not used. :P Cheers Nikhil jindal On Thu, Aug 13, 2009 at 7:38 PM, ankur aggarwal <[email protected]>wrote: > @angad > read the ques carefully ... > wat r u saying ??? > try 2 explain .. > > > 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 -~----------~----~----~----~------~----~------~--~---
