If the numbers in the array continuous .. then it is very simple by using Arithmetic Progression . we can sum up the all the numbers in an array and subtract Arithmetic Progression sum..we will get...O(n)..
or in one trace we can find min and max numbers in that array.. bitset <(max-min)> duplicates; for(int i=0;i<n;i++) { if(duplicates[array[i]-min] ==1) print duplicate... else duplicate[array[i]-min]=1; } On Wed, Aug 31, 2011 at 2:02 AM, Navneet Gupta <navneetn...@gmail.com>wrote: > You are given an array. One integer is in the array twice and others > are unique. Find that no. O(n) Solution > > -- > Regards, > Navneet > > -- > 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> -- 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.