problem statement can be found here
this is really a cool problem. the problem asks us to find find the minimum number of terms(integers) to add to the set of sorted integers in order to obtain an Arithmetic Progression.
let d be the difference of the arithmetic progression.
as we know that Pi – Pi-1 is k*d so any common factor for all the differences between the given adjacent terms can be our d, but since we have to add minimum number of terms d should be as large as possible so the common factor…
once we obtain the d it is easy to find the number of missing terms..
this problem can be solved using memoization, but it took some time to formulate the paths..
problem statement is available from here
all that we have to do is print the matrix in spiral order. and to solve it in a easy way we can first coat-up the matrix with a boundary(None) and try to shrink it as we move on(printing).
this is a question from codereview
the key thing to observe is that if we go on to add the elements in a set, at some point the size of set doesn’t increase….
the key idea is to use the quicksort partitioning scheme in which we reduce our selection problem size into half(just the expectation).
T(n) = O(n) + T(n // 2)
the resulting algrithm is a O(n) algo…
if anyone faced a problem similar to RMID2 but having very less queries but large data stream then it is better to use the randomized selection’s
O(1) insertion and
O(n) query rather than two priority queue method’s
O(log(n)) insertion and
here’s my implementation..
simple math problem. although n^2 logn algo is obvious this question can also be solved using an n^2 algo which is better one.