# spoj 8132. Street Trees | STREETR

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..

https://gist.github.com/3c44f3fecd9b2208bcaa

# Randomized Selection Algorithm

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 `O(log(n))` query..

here’s my implementation..

https://gist.github.com/929264ea9a05aa0956c5