Remove as many 3's that would make it 1000. The example still holds
@gauri: the logic is that if your pivot is greater than all numbers till middle then it would not effect the middle element. Hence if middle element is not the mode in the given array, the answerwould be wrong. On 4/15/10, vivek bijlwan <[email protected]> wrote: > @rohit : thats more than 1000 elements in the array > > On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf > <[email protected]>wrote: > >> say u choose the last value as pivot >> >> 1 1 1 1 1 1 1 ............(499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4 >> >> 4 is your pivot >> try out >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> On Thu, Apr 15, 2010 at 5:26 PM, vivek bijlwan <[email protected]> wrote: >> >>> @rohit : can you give me any counter examples? >>> >>> PS: one value is occuring >=501 times. >>> >>> On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf <[email protected] >>> > wrote: >>> >>>> It cannot just be partitioned in such a manner that the middle element >>>> is >>>> *always *the mode ! >>>> >>>> -------------------------------------------------- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>> >>>> >>>> On Thu, Apr 15, 2010 at 11:23 AM, Gauri <[email protected]> wrote: >>>> >>>>> Can you illustrate it with an example ? >>>>> How are you deciding the pivot for partitioning the array ? >>>>> How the middle element can be the mode of the array ? >>>>> >>>>> Regards >>>>> Gauri >>>>> >>>>> >>>>> On Apr 14, 5:39 pm, vivek bijlwan <[email protected]> wrote: >>>>> > complexity : On) >>>>> > extra - memory required : no >>>>> > >>>>> > have the first iteration of quick sort. return the middle element. >>>>> > >>>>> > >>>>> > >>>>> > On Wed, Apr 14, 2010 at 4:14 PM, Gauri <[email protected]> wrote: >>>>> > > Say If I have an array of 1,000 32-bit integers .And one of the >>>>> value >>>>> > > is occuring 501 number of times or more in the array. Can someone >>>>> help >>>>> > > me devise an efficient algorithm for the same ? >>>>> > >>>>> > > Thanks & Regards >>>>> > > Gauri >>>>> > >>>>> > > -- >>>>> > > You received this message because you are subscribed to the Google >>>>> Groups >>>>> > > "Algorithm Geeks" group. >>>>> > > To post to this group, send email to [email protected]. >>>>> > > To unsubscribe from this group, send email to >>>>> > > [email protected]<algogeeks%[email protected]> >>>>> <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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]<algogeeks%[email protected]> >>>>> . >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[email protected]> >>>> . >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Sent from my mobile device -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
