How about doing like below ?. Assume we have the elements like {12, 3, 4, 15, 9, 9, 4, 12 }
Binary representation {1100, 0011, 0100, 1111, 1001, 1001, 0100, 1100 } Step 1: Check the left most bit and separate them 0 and 1's. {0100, 0011, 0100, 1111, 10001, 1001, 1100, 1100 } Step 2: Now divide into two problems based on the number of 0's and 1's of the bit that you have checked in the step1 {0100, 0011, 0100} {1111, 10001, 1001, 1100, 1100 } Step 3: Take the next bit from the left and repeat the same like step1 and continue Thanks, Sathaiah On Tue, May 18, 2010 at 7:11 PM, CHERUVU JAANU REDDY < jaanu.cher...@gmail.com> wrote: > > Here u r using extra space to store count values.. > > > > ---------------------------------------- > CHERUVU JAANU REDDY > M.Tech in CSIS > > > > On Tue, May 18, 2010 at 7:01 PM, Jagadish M <jagadis...@gmail.com> wrote: > >> >> On May 18, 8:29 am, Terence <technic....@gmail.com> wrote: >> > How do you maintain the heap? Could you explain in detail for the >> > following example: >> > 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) >> >> Basically, in each node we maintain the key and its count. >> >> Initially, heap has the first element. >> 1:1 >> >> Search for 2 and insert( since its not found) >> 1:1 >> / >> 2:1 >> >> Search for 3 and insert ( since its not found). >> >> 1:1 >> / \ >> 2:1 3:1 >> >> Search for 3; since 3 is already there increment its count by 1. >> >> 1:1 >> / \ >> 2:1 3:2 >> >> Search for 2; since 2 is already there increment its count by 1. >> >> 1:1 >> / \ >> 2:2 3:2 >> >> and so on... >> >> >> Since, there are only k distinct keys the heap size will at most be k; >> so each search/insert/increment operation takes O(log k) time. >> >> >> Jagadish >> http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> >> >> >> >> > >> > On 2010-5-17 22:38, Jagadish M wrote: >> > >> > >> > >> > > The best algorithm I can think of is to maintain a heap of k elements. >> > > Takes O(n log k) time. >> > > Is anything told about the values of the keys? If the keys have values >> > > less than N, then it is possible to do >> > > what you say, i.e sort them in place. >> > >> > > -Jagadish >> > >http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> >> > >> > > On May 13, 7:06 pm, divya<sweetdivya....@gmail.com> wrote: >> > >> > >> This problem was asked in google phone interview. We have N element >> > >> array with k distinct keys(No relation between k& N given so assume >> > >> k<N) >> > >> What is the best method to sort this array without using any extra >> > >> memory? Please elaborate. >> > >> > >> -- >> > >> You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> > >> To post to this group, send email to algoge...@googlegroups.com. >> > >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> > >> For more options, visit this group athttp:// >> 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 algoge...@googlegroups.com. >> > To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> > For more options, visit this group athttp:// >> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.