O(n) approach for finding the height of the stacks..
-----------------------------------------------------
First take 2 arrays A[n] and B[n],
where A keeps track of the no. of times a start index(the start query
index) occurs.
and B keeps track of the no. of times a end index(the end query index)
occurs.
Also,
take an array C[n] to store height of each stack..
To calculate the height of a particular stack we can use the following
logic:
As we know that if the end index is say 'R' then start index would be
<= 'R'.
Hence, for a given stack index 'X' , we can calculate its height by
using the following equation:
C[X] = (no. of start indices strictly lesser than (<) 'X') - (no. of
end indices strictly lesser than (<) 'X') + A[X]
-----------------------------------
O(K) approach to get the median stack
------------------------------------------------------------
As there are only 'K' instructions, it implies that the height of the
stack will be <='K'.
Hence, let take an array S[K+1] ( 0..K) to keep track of the no. of
stacks with height 'i'(say) given by S[i]..
To do this we have to run through array C and generate S, as follows:
for(int i =0; i <n; ++i)
++S[C[r]];
As the median stack is the (N+1)/2 'th stack, we can use array S to
get the height of the median stack as follows:
int x = (N+1)/2;
for(int i =0; i <=k; ++i)
{
if(x > S[i])
x= x- S[i];
else
break;
}
// after the loop breaks 'i' will be the height of the median stack..
On May 13, 8:42 pm, Krishnan <aariyankrish...@gmail.com> wrote:
> @ashish pant
> We must compute all the queries in O(n)+O(k).
>
> We must have array like counting array.
>
> It is not my logic but my friend told about this logic
--
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.
