# Radio transmitters challenge

**Problem statement**

Hackerland is a one-dimensional city with houses, where each house is located at some on the x-axis. The Mayor wants to install radio transmitters on the roofs of the city’s houses. Each transmitter has a range, , meaning it can transmit a signal to all houses units of distance away.

Given a map of Hackerland and the value of , can you find and print the minimum number of transmitters needed to cover every house in the city? (Every house must be covered by at least one transmitter) Each transmitter must be installed on top of an existing house.

**Input Format**

The first line contains two space-separated integers describing the respective values of (the number of houses in Hackerland) and (the range of each transmitter).

The second line contains space-separated integers describing the respective locations of each house (i.e., ).

**Constraints**

There may be more than one house at the same location.

**Output Format**

Print a single integer denoting the minimum number of transmitters needed to cover all the houses.

**Sample Input 0**

5 1 1 2 3 4 5

**Sample Output 0**

2

**Explanation 0**

The diagram below depicts our map of Hackerland:

We can cover the entire city by installing transmitters on houses at locations and . Thus, we print on a new line.

**Sample Input 1**

8 2 7 2 4 6 5 9 12 11

**Sample Output 1**

3

**Explanation 1**

The diagram below depicts our map of Hackerland:

We can cover the entire city by installing transmitters on houses at locations , , and . Thus, we print on a new line.

**Solution**

The first we are going to take is sort the array `x`

:

Arrays.sort(x);

Next, we are going to iterate over all the elements using a cursor `i`

. As long as the current house, `x[i]`

is within points from the last transmitter-covered house, `x[last]`

, we keep incrementing `i`

. When we reach a house that is more than points from the last transmitter-covered house, we know that we need to place one more transmitter. So we increment our transmitter count (`ans`

) and update `last = i - 1`

. We have now covered the left side of the transmitter. Since a transmitter can cover two sides, left and right, we need to increment our cursor `i`

as long as `x[i]`

is within distance from `last`

, for the right side. Once we are out of range we update `last`

accordingly, but don’t place a new transmitter. We repeat the process for the left and right side until we have iterated over all houses.

The sorting part has a running time of while the iteration over all the houses has a running time of . The full code is available below.

**Full code**

public class RadioTransmitters { private static int solve(int[] x, int k) { int ans = 0; Arrays.sort(x); int n = x.length; int last = 0; int i = 0; while (i < x.length) { while (i < n && x[i] <= x[last] + k) { i++; } ans++; last = i - 1; while (i < n && x[i] <= x[last] + k) { i++; } last = i; } return ans; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int[] x = new int[n]; for (int i = 0; i < n; i++) { x[i] = in.nextInt(); } System.out.println(solve(x, k)); } }