Fence Post Problem
Problem
A straight fence is L meters long. A pole is placed at both ends and then every d meters. L is a multiple of d. Read L and d and print how many poles are needed. Example: L = 10, d = 2 needs 6 poles.
Constraints
- 1 <= d <= L <= 10^9
- L % d == 0
Examples
Input
10 2
Output
6
Solutions
This is the off-by-one (fence-post) error. N gaps have N + 1 posts. The same idea explains why a loop from a to b has b - a + 1 steps.
/*
* Problem : Count the poles of a straight fence.
* Input : Fence length L and distance d between poles.
* Output : The number of poles.
* Approach: Poles = segments + 1.
* Time : O(1)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long length = scanner.nextLong();
long distance = scanner.nextLong();
// Step 1: Count the gaps between poles. Example: 10 meters with 2 meters gaps -> 5 gaps.
long gaps = length / distance;
// Step 2: One more pole than gaps, because both ends have a pole.
long poles = gaps + 1;
// Step 3: Print the result.
System.out.println(poles);
}
}
Hints (1)
- Draw a fence with 2 gaps. How many poles?