@Bharatkumar: You've tacitly assumed that the data values are in the range 0 to n-1. That's not given in the problem statement.
Dave On Aug 31, 1:16 am, bharatkumar bagana <bagana.bharatku...@gmail.com> wrote: > bitset <n> duplicates;// n- bit space.. > for(int i=0;i<n;i++) > { > if(duplicates[array[i]] ==1) > print duplicate... > else duplicate[array[i]]=1;} > > there is no comparison between any 2 numbers ....O(n) time .....space is > O(n)bits ... > > > > > > On Tue, Aug 30, 2011 at 5:18 PM, Dave <dave_and_da...@juno.com> wrote: > > Replying to myself... A radix sort takes O(n) extra space. > > > Dave > > > On Aug 30, 1:49 pm, Dave <dave_and_da...@juno.com> wrote: > > > @Kamakshii: With O(1) extra space, it can be done with O(n) > > > comparisons. Do a radix sort on the input (no comparisons), and then > > > check adjacent numbers for equality. > > > > Dave > > > > On Aug 30, 1:34 pm, Kamakshii Aggarwal <kamakshi...@gmail.com> wrote: > > > > > develop an algorithm to find duplicates in a list of numbers without > > using a > > > > binary tree..if there are n distinct numbers in the list ,how many > > times > > > > must two numbers be compared for equality in your algorithm?what if all > > > > numbers are equal? > > > > > -- > > > > Regards, > > > > Kamakshi > > > > kamakshi...@gmail.com- Hide quoted text - > > > > - Show quoted text - > > > -- > > 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. > > -- > > **Please do not print this e-mail until urgent requirement. Go Green!! > Save Papers <=> Save Trees > *BharatKumar Bagana* > **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> > * > Mobile +91 8056127652* > <bagana.bharatku...@gmail.com>- Hide quoted text - > > - Show quoted text - -- 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.