@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.
