HackerRank Hackerland Radio Transmitters problem solution

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

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)

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;
}