Coder
BAN USERFinding an i th maximum can be done in log n time using Augmented Red Black Tree.
In red black tree, in each node add one more data, that is size
Size is calculated as (size of left subtree) + (size of right subtree) + 1.
Now once the tree is build, question is how to find i th maximum.
We'll start checking from root.
r = size[left[node]]+1
There are 3 cases:
1. if i == r, then root is the answer
2. if i < r, then search for i th maximun in left subtreee
3. if i > r, then search for (i - r) the maximum in right subtree.
In the worst case, you have to travel from root to leaf node, therefore worst case running time is log n.
1.
Modular Exponential problem
N <= 1000, that means N can be expressed in 10 bits
function modular_pow(base, exponent, modulus)
result := 1
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base = (base * base) mod modulus
return result
modular_Pow(N, N, K)
since exponent N is 10 bit, while loop will iterate 10 times.
If the return result is 0 then N^N is divible by K
running time of this alogithm is (log N)
To find out a node where interval overlaps, it take lg n time.
Since there can be multiple nodes where interval overlaps it will take K lg n time where K is the number of nodes where interval overlaps.
Procedure to find out node:
1. Build red black tree
2. search for a node
3. if found delete that node and again search for other node
this is Output Sensitive Algorithm
use an augmented red black tree, to build an interval tree. Each node maintains interval and max value apart from pointer.
Search for particular time can be performed in lg n time.
If there are say K occurences where interval overlaps, it will take O(K * lg n) time.
Repsheenaamajors, System Administrator at Achieve Internet
Teach art classes to a diverse array of students of varying ages and abilities. Strong desire to incorporate a multidimensional ...
@shagun: i didn't get how the remainder will never exceeds 9
- Coder July 02, 2012take example of n = 13
in first iteration: r = 1 and num = 11
in next iteration: r = 11