Can we have some mathematical logic behind this. Can we generalise it ?
Regards ,
Gauri
On 4/15/10, Rohit Saraf 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 : thats more than 1000 elements in the array
On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf 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
>
>
I feel gaurav's solution does it in O(n) time & cons space
but there is a case that when there is no element with n/2+1
appearances the method might fail(eg 1 1 1 2 3 4 and in many other
cases as well...)
but as the problem states that there is atleast 1 element with n/2+1
appearancesthis a
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.ii
@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 wrote:
> It cannot just be partitioned in such a manner that the middle element is
> *always *the mode !
>
> --
> Roh
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
On Thu, Apr 15, 2010
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 wrote:
> complexity : On)
> extra - memory required : no
>
> have the first iteration of qui
