##
__STREET TREES __

Link to the question: STREETR

###
__HOW TO APPROACH:__

The question asks us to find the minimum number of trees which must be planted so that the distance between the adjacent trees is same. Hence we find the gcd of the difference between the adjacent trees, and then divide the difference with the gcd and it.

##
__SOLUTION :__

/* Street Trees (STREETR) */

/* -Susahnt Gupta */

#include<stdio.h>

long long int gcd(long long int a, long long int b)

{

if(b>a)

return gcd(b,a);

else if(b!=0)

return gcd(b,a%b);

else

return a;

}

int main()

{

int t,i;

scanf("%d",&t);

long long int a[t],h,diff,s=0;

for(i=0;i<t;i++)

scanf("%lld",&a[i]);

h= a[1]-a[0];

for(i=1;i<t;i++)

{

diff= a[i]- a[i-1];

h= gcd(diff,h);

}

for(i=1;i<t;i++)

{

diff= a[i]- a[i-1];

s= s+ (diff/h)- 1;

}

printf("%lld\n",s);

return 0;

}

this will not work if input is not sorted .

ReplyDeleteYeah, but you can assume that the input is sorted as can be read from the comments of the question.

Delete