A group of trees is planted along a straight line.

KOI is planning to plant more trees so that the distance between two adjacent trees is equal for all trees.

For simplicity, each tree can only be planted on an integer coordinate.

**Problem:** Sphere Online Judge (SPOJ) – Problem STREETR

**Solution:**

To illustrate this problem I drew this small graphic:

The large trees are given and we have to find the small ones. You can see pretty fast that the maximum difference between trees is the minimum difference between already planted trees. But we’re not only looking for one arbitrary solution (which would be zero difference), we’re looking for the greatest difference or more generally the Greatest common divisor.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
def gcd(a, b): if b == 0: return a else: return gcd(b, a % b) def gcdList(lst): myGcd = gcd(lst[0], lst[1]) for c in lst[1:]: myGcd = gcd(myGcd, c) return myGcd N = int(raw_input()) diff = [] lastTree = int(raw_input()) for i in xrange(1, N): newTree = int(raw_input()) diff.append(newTree - lastTree) lastTree = newTree myGcd = gcdList(diff) trees = map(lambda x: (x / myGcd) - 1, diff) print sum(trees) |