Hackerland Radio Transmitters

Hackerland is a one-dimensional city with houses aligned at integral locations along a road. The Mayor wants to install radio transmitters on the roofs of the city's houses. Each transmitter has a fixed range meaning it can transmit a signal to all houses within that number of units distance away.

Given a map of Hackerland and the transmission range, determine the minimum number of transmitters so that every house is within range of at least one transmitter. Each transmitter must be installed on top of an existing house.

Example:

Input: n =5, k= 1, arr[n]={1,2,3,4,5}
Output: 2

Approach

Java

import java.util.Arrays;

public class HackerlandRadioTransmitters {
    public static void main(String[] args) {
        int k = 1;
        int arr[] = { 1, 2, 3, 4, 5 };
        System.out.println(hackerlandRadioTransmitters(arr, k));

    }

    static int hackerlandRadioTransmitters(int[] arr, int k) {
        // sort the array
        Arrays.sort(arr);
        int ind = 0;
        int i = 1;
        int cnt = 0;
        int n = arr.length;
        while (i < n) {
            while (i < n && arr[i] - arr[ind] <= k)
                i++;
            ind = i - 1;
            while (i < n && arr[i] - arr[ind] <= k)
                i++;
            ind = i;
            cnt++;
        }
        if (cnt == 0)
            return 1;
        else
            return cnt;

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int hackerlandRadioTransmitters(vector<int> arr, int k)
{

    //sort the array
    sort(arr.begin(), arr.end());
    int prev = arr[0];
    int ind = 0;
    int i = 1;
    int cnt = 0;
    int n = arr.size();
    while (i < n)
    {
        while (i < n && arr[i] - arr[ind] <= k)
            i++;
        ind = i - 1;
        while (i < n && arr[i] - arr[ind] <= k)
            i++;
        ind = i;
        cnt++;
    }
    if (cnt == 0)
        return 1;
    else
        return cnt;
}

int main()
{
    int n = 5, k = 1;
    vector<int> arr = {1, 2, 3, 4, 5};

    cout << hackerlandRadioTransmitters(arr, k);
    return 0;
}