STREETR - Street Trees
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.
For example, if 4 trees were originally planted on coordinates (1, 3, 7, 13), and if KOI plants 3 more trees on coordinates (5, 9, 11), then the distance between two adjacent trees will equal for all trees.
Your task is to calculate the minimal number of trees that KOI can plant so that the distance between two adjacent trees will equal for all trees.
Input
The first line is an integer N (3 <= N <= 100,000), which denotes the number of already planted trees.
The next N lines will have an integer X (1 <= X <= 1,000,000,000), which denotes the coordinate of each tree.
You can safely assume that the value of X will be unique.
Output
Output the minimal number of trees that must be planted.
Example
Input: 4 1 3 7 13 Output: 3
Input: 4 2 6 12 18 Output: 5
[Edited] Warning: Some input file contains garbage at the end.
hide comments
arpitkath:
2015-07-16 17:08:26
nice use of Arithmetic Progression |
|
Dushyant Singh:
2015-06-16 09:31:08
Don't know how people did it in O(n). I did it in O(3*n). :-( |
|
[Mayank Pratap]:
2015-05-18 08:23:34
No need to sort!! Last edit: 2015-05-18 08:28:53 |
|
GAURAV CHANDEL:
2015-03-31 22:46:08
Nice math...O(n) sol. |
|
Satyam Mishra:
2015-01-19 21:54:19
ACed with O(n) solution.. |
|
SHIVAM DIXIT:
2014-09-28 13:52:52
input is already sorted... |
|
Shaktiman:
2014-07-11 15:25:53
are terms in increasing order? |
|
agaurav77:
2014-05-26 20:43:09
O(n) solution works fine. Phew, AC! |
|
AVOID:
2014-03-28 12:40:06
int sufficient
|
|
saket diwakar:
2013-01-16 14:00:29
finally found the error....
|
Added by: | Lawl |
Date: | 2011-01-05 |
Time limit: | 0.203s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | 2010 KOI High School Division |