Counting sort does not run in O(1) space though. Optimally it will run in O(K) space, where A is an array of integer numbers and K = max(A) - min(A)
On Saturday, February 9, 2013 9:52:01 PM UTC-5, Mohanabalan wrote: > can use counting sort > > > On Sun, Jul 15, 2012 at 6:37 PM, santosh thota > <[email protected]<javascript:> > > wrote: > >> If we can retrieve ith prime efficiently, we can do the following... >> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime >> 2.check if (prod% (ith_prime * ith_prime )==0) then return i; >> else prod=prod*ith_prime; >> 3.repeat it till end >> >> >> >> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: >> >>> Given an array of integers where some numbers repeat once, some numbers >>> repeat twice and only one number repeats thrice, how do you find the number >>> that gets repeated 3 times? >>> >>> Does this problem have an O(n) time and O(1) space solution? >>> No hashmaps please! >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. >> >> To post to this group, send email to [email protected]<javascript:> >> . >> To unsubscribe from this group, send email to >> [email protected] <javascript:>. >> 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 unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
