Tuesday, 30 June 2015

STREETR

Standard

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.

RECOMMENDED QUESTION :

Try this very easy question.

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;
}

2 comments:

  1. this will not work if input is not sorted .

    ReplyDelete
    Replies
    1. Yeah, but you can assume that the input is sorted as can be read from the comments of the question.

      Delete