HackerRank Hackerland Radio Transmitters problem solution

In this HackerRank Hackerland Radio Transmitters problem solution, 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.

Function Description

Complete the hackerlandRadioTransmitters function in the editor below.

hackerlandRadioTransmitters has the following parameter(s):

• int x[n]: the locations of houses
• int k: the effective range of a transmitter

Returns

• int: the minimum number of transmitters to install

HackerRank Hackerland Radio Transmitters problem solution in Python.

n,k = input().strip().split(' ')
n,k = [int(n),int(k)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
x.sort()
l = list()
#To remove duplicates
l = [0 for i in range(100001)]
for i in x:
    l[i-1] = 1
    #print(i)
x = []
for i in range(100001):
    if l[i] == 1:
        x.append(i+1)
#print(x)
start = 0
i = 0
c = 1
n = len(x)
while i < n:
    if x[i] <= x[start] + k:
        i = i + 1
        continue
    else:
        s = i-1
        while i < n and x[s] + k >= x[i]:
            i += 1
        start = i
        if i < n:
            c += 1
print(c)

Hackerland Radio Transmitters problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] x = new int[n];
        for(int x_i=0; x_i < n; x_i++){
            x[x_i] = in.nextInt();
        }
        Arrays.sort(x);
        int total = 0;
        boolean over = false;
        for(int j = 0; j < x.length; j++) {
            System.err.print(x[j] + " ");
        }
        for(int i = 0; i < x.length; i++) {
            int current = x[i];
            for(int j = i+1; j <  x.length && x[j] <= current+k; j++){
                i++;
            }
            current = x[i];
            total++;
            for(int j = i+1; j < x.length && x[j] <= current+k; j++){
                i++;
            }
            
        }
        System.out.println(total);
       
    }
}

Problem solution in C++.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<int> x(n);
    for(int x_i = 0;x_i < n;x_i++){
       cin >> x[x_i];
    }
    sort(x.begin(), x.end());
    int lastRadio = -k - 1;
    int firstHouse = x[0];
    int radios = 0;
    for (int i = 1; i < n; i++) {
        if (x[i] > firstHouse + k) {
            lastRadio = x[i - 1];
            radios++;
            while (i < n && x[i] <= lastRadio + k) {
                i++;
            }
            if (i < n) {
                firstHouse = x[i];
            }
        }
    }
    if (x[n - 1] > lastRadio + k) {
        radios++;
    }
    cout << radios << 'n';
    return 0;
}

Problem solution in C.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

void quick_sort (int *a, int na) {
    if (na < 2)
        return;
    
    int p = a[na / 2];
    int *l = a;
    int *r = a + na - 1;
    
    while (l <= r) {
        if (*l < p) {
        	l++;
            continue;
        }
        if (*r > p) {
            r--;
            continue;
        }
        
        int t = *l;
        *l++ = *r;
        *r-- = t;
    }
    
    quick_sort(a, r - a + 1);
    quick_sort(l, a + na - l);
}

int main(){
    int n, k, cnt, min, cur; 
    
    scanf("%d %d", &n, &k);
    int *x = malloc(sizeof(int) * n);
    
    for (int i = 0; i < n; i++)
       scanf("%d", &x[i]);
    
    quick_sort(x, n);
    
    cnt = 1;
    cur = min = x[0];
    for (int i = 1; i < n; i++) {
        if (x[i] - min <= k) {
            cur = x[i];
        }
        
        if (x[i] - cur > k) {
            cur = min =  x[i];
            cnt++;
        }
    }
        
    printf("%dn", cnt);
    
    return 0;
}