Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Radio transmitters challenge

Sharing is caring!

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

Given a map of Hackerland and the value of k, 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 n (the number of houses in Hackerland) and k (the range of each transmitter).
The second line contains n space-separated integers describing the respective locations of each house (i.e., x_1, x_2,\dots,x_n).

Constraints
1 \le n, k \le 10^{5}
1 \le x_i \le 10^{5}
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 2 and 4. Thus, we print 2 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 4, 9, and 12. Thus, we print 3 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 x_i using a cursor i. As long as the current house, x[i] is within k points from the last transmitter-covered house, x[last], we keep incrementing i. When we reach a house that is more than k 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 k 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 \mathcal{O}(nlogn) while the iteration over all the houses has a running time of \mathcal{O}(n). 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));
    }
}