i don't think there is an O(n) time solution for this... bcoz there are no constraints on the values, and on the number of values in the array.
On Thu, Nov 24, 2011 at 7:15 PM, kumar raja <rajkumar.cs...@gmail.com>wrote: > @shady : i am not sure , if u can do it with O(n) space as well it is fine > for me . but once try whether it is possible in O(1) space. > > > On 24 November 2011 05:42, shady <sinv...@gmail.com> wrote: > >> "find it in O(n) time and O(1) space", >> are you sure that it is possible to do it in O(n) time ? >> >> On Thu, Nov 24, 2011 at 6:59 PM, kumar raja <rajkumar.cs...@gmail.com>wrote: >> >>> @ravu sairam: >>> >>> Suppose the hashing is banned ,now what is ur solution??? >>> Hashing is quite theoretical concept with time complexity O(1). >>> >>> But it will not be the case every time.so suggest some other better >>> solution >>> >>> I used to thought of using count array ,but again its size is not O(n), >>> its size should be max-min+1 . >>> and it looks odd. so even if someone want to provide linear time >>> solution using extra space in O(n) it is welcome... >>> >>> >>> On 24 November 2011 05:13, shady <sinv...@gmail.com> wrote: >>> >>>> hashing is not that simple, can you tell your hash function ? >>>> >>>> >>>> On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam <ravu...@gmail.com> wrote: >>>> >>>>> I have an O(n) space and time solution by using hashing . Firstly, >>>>> make a hash table by using a hash function for each of the number in >>>>> the array. After that, go through the hash table to see whether there >>>>> are any repetitions for the same entry. >>>>> >>>>> -- >>>>> 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. >>>> >>> >>> >>> >>> -- >>> Regards >>> Kumar Raja >>> M.Tech(SIT) >>> IIT Kharagpur, >>> 10it60...@iitkgp.ac.in >>> >>> >>> -- >>> 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. >> > > > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in > > > -- > 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.
