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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s