On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
Construct a binary tree from the data (maintain the size of subtree under
each node).
Do rotations till the left subtree does not have size k. Rotation is a
constant time operation.
Please prove the correctness of your
@Dave n Harshi, thanks for your answer.
I am still not clear very much . May be u can help in elucidating your
replies.
If such a tree is degenerate, then the complexity of search is O(n), but if
it is a well-balanced tree, where some nodes may have 'k' children and some
nodes may have 'm'
Time complexity is O(n log n). But the last solution I gave has O(n).
What did u not understand abt thesolution
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Time complexity is O(n log n). But the last solution I gave has O(n).
What did u not understand abt thesolution
@Rohit Please explain how that Binary tree solution works.
On 11 April 2010 21:56, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
Time complexity is O(n log n). But the last solution I gave has O(n).
What did u not understand abt the solution
Median of medians is a decent algorithm for extracting the kth element( an
element of kth rank ).
I
On 11 April 2010 11:06, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
I realised now that it can be done easily as :
we can find the kth largest element in O(n) using Linear general
selection algorithm - Median of Medians algorithm
Well , can we do better than O(n log n ) in creating a BST
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
take a look at this link . The running time is less than 2 sec for 10^8.
On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond patidarc...@gmail.comwrote:
i have an problem on SPOJ to find all the prime less than 10^8
Hi, Black DiamonThere is a trick that number that can be devided by 2 or 3
is ignored, so we just deal with number 6n + 1 and 6n + 5, so you can try
this:
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
int table = 4;
Not only even numbers, but you can extend the algorithm for other numbers as
well.
Start with 2, mark all the numbers which are multiples of 2,
then in the next iteration, take 3, and mark all the numbers which are
multiples of 3.
If a number is already marked, you dont consider that number in
how to store fractional numbers with a fractional part having 25-30
digits after decimal place,
does long double has the same precision as double?.
1 more prob.
format specifier for long double is %lf and same for double, so if i
write
long double a;
scanf(%lf,a);
a=a*2;
once u get kth element , u can find first k by a linear travel through the array
On 4/11/10, Priyanka Chatterjee dona.1...@gmail.com wrote:
On 11 April 2010 11:06, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
I realised now that it can be done easily as :
we can find the kth largest
but still the binary tree solution is of more practical use.i will
explain the solution once i reach my comp
On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
Time complexity is O(n log n). But the
12 matches
Mail list logo
