Grid Posts Along a Fence
EasyMath & Geometry
Problem
A straight fence runs between two posts at integer grid points (x1, y1) and (x2, y2). Extra posts can only stand at points where both coordinates are integers.
Return how many integer grid points lie on the fence, including both ends.
Example 1
- Input:
- x1 = 0, y1 = 0, x2 = 6, y2 = 4
- Output:
- 3
(0, 0), (3, 2) and (6, 4).
Example 2
- Input:
- x1 = 0, y1 = 0, x2 = 0, y2 = 5
- Output:
- 6
A vertical fence passes through every integer y from 0 to 5.
Example 3
- Input:
- x1 = 2, y1 = 3, x2 = 2, y2 = 3
- Output:
- 1
Both ends are the same point.
Constraints
- -10^9 ≤ x1, y1, x2, y2 ≤ 10^9
Hint
Show the first hint
Walk from one end to the other in the smallest possible integer step.
Walkthrough
How to approach it
01Clarify before coding
- Are both ends counted? Yes.
- Can the two points coincide? Yes, the answer is then 1.
- Can coordinates be negative? Yes; only the differences matter.
02Brute force
For each integer x between x1 and x2, check whether the matching y on the segment is an integer (handling vertical fences separately).
Cost: O(|dx|): up to 2 · 10^9 checks, plus fiddly special cases.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.