Sign in Subscribe
By Vishal Basumatary in Hackerrank —

Hackerrank Hackerland Radio Transmitters Solution

Hackerrank Hackerland Radio Transmitters Solution

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.

For example, assume houses are located at  and the transmission range .   antennae at houses  and  and  would provide complete coverage.  There is no house at location  to cover both  and .  Ranges of coverage, are , , and .

Function Description

Complete the hackerlandRadioTransmitters function in the editor below.  It must return an integer that denotes the minimum number of transmitters to install.

hackerlandRadioTransmitters has the following parameter(s):

  • x: integer array that denotes the locations of houses
  • k: an integer that denotes the effective range of a transmitter

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The first line contains two space-separated integers  and , 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 .

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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

Subtasks

  • for  of the maximum score.

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Print a single integer denoting the minimum number of transmitters needed to cover all of 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:

k-nearest(2).png

We can cover the entire city by installing  transmitters on houses at locations  and .

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:

k-nearest2(2).png

We can cover the entire city by installing  transmitters on houses at locations , , and .

Solution in java8

Approach 1.

import java.util.Scanner;
import java.util.Arrays;

public class Solution {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int k = in.nextInt();

		int[] p = new int[n];
		for (int i = 0; i < n; ++i) p[i] = in.nextInt();

		Arrays.sort(p);
	
		int uncover = 0;
		int lamp = -1;
		int count = 0;

		for (int i = 1; i < n; ++i){
			if (uncover <= lamp && p[i] - p[lamp] > k) uncover = i;
  
			if (uncover > lamp && p[i] - p[uncover] > k) {
				++count;
				lamp = i - 1;
				--i;
			}
		}

		if (lamp == -1 || p[n - 1] - p[lamp] > k) {
			++count;
			lamp = n - 1;
		}

		System.out.println(count);
	}
}

Approach 2.

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

public class Solution {

    static int hackerlandRadioTransmitters(int[] x, int k) {
            Arrays.sort(x);
		 	int numOfTransmitters = 0;
		 	int i = 0;
		 	while (i < x.length) {
		 	    numOfTransmitters++;
		 	    int loc = x[i] + k;
		 	    while (i < x.length && x[i] <= loc) 
		 	    {
		 	    	i++;
			 	    
		 	    }	
		 	    loc = x[--i] + k;
		 	    while (i < x.length && x[i] <= loc)
		 	    {
		 	    	i++;
		 	    }
		 	}
		 	return numOfTransmitters;
    }

    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();
        }
        int result = hackerlandRadioTransmitters(x, k);
        System.out.println(result);
        in.close();
    }
}

Approach 3.

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

public class Solution {

    static int hackerlandRadioTransmitters(int[] x, int k, int n) {
        // Complete this function
        Arrays.sort(x);
        int numOfTransmitters = 0;
        int i = 0;

        while (i < n ) {
            numOfTransmitters++;
            int loc = x[i] + k;
            
            while (i < n && x[i] <= loc) i++;
            loc = x[--i] + k; 
            while (i < n && x[i] <= loc) i++;
        }
        
        return numOfTransmitters;

    }

    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();
        }
        int result = hackerlandRadioTransmitters(x, k, n);
        System.out.println(result);
        in.close();
    }
}

Solution in python3

Approach 1.

n, k = map(int, input().split())
x = sorted(list(set(list(map(int, input().split())))))
n = len(x)

count, first_uncovered = 0, 0
while first_uncovered < n:
  i = first_uncovered
  while i < n and x[i] - x[first_uncovered] <= k:
    i += 1
  while first_uncovered < n and x[first_uncovered] - x[i - 1] <= k:
    first_uncovered += 1
  count += 1
print(count)

Approach 2.

n, k = [int(i) for i in input().split()]
H = [0]*(10**5 + 1)
x = [int(i) for i in input().split()]
min_index = x[0]
max_index = x[0]
for i in x:
    H[i] = 1
    min_index = min(min_index, i)
    max_index = max(max_index, i)
r = 0
i = min_index
while(i <= max_index):
    r += 1
    j = i + k
    if (j <= max_index):
        while(H[j] != 1 and j > i):
                j -= 1
    i = j + k + 1
    while (i <= max_index and H[i] != 1):
        i += 1

print(r)

Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the hackerlandRadioTransmitters function below.
def hackerlandRadioTransmitters(x, k):
    count=0
    i=0
    x.sort()
    n=len(x)
    while i<n:
        count=count+1
        loc=x[i]+k
        while i<n and x[i]<=loc:
            i=i+1
        loc=x[i-1]+k
        while i<n and x[i]<=loc:
            i=i+1
    return count
    


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    x = list(map(int, input().rstrip().split()))

    result = hackerlandRadioTransmitters(x, k)

    fptr.write(str(result) + '\n')

    fptr.close()

Solution in cpp

Approach 1.

#include <iostream>
#include <vector>
#include <algorithm>
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];
    }
    int i=0;
    sort(x.begin(),x.end());
    int count=0;
    int loc;
    while(i<n){
        count++;
        loc=x[i]+k;
        while(i<n && x[i]<=loc)
            i++;
        i--;
        loc=x[i]+k;
        while(i<n && x[i]<=loc)
            i++;
    }
    cout<<count;
    return 0;
}

Approach 2.

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


int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<int> a(n);
    for(int x_i = 0;x_i < n;x_i++){
       cin >> a[x_i];
    }
    
    sort(a.begin(),a.end());
    a.erase( unique( a.begin(), a.end() ), a.end() );
    
    int count=0;
    int i=0;
    while(i<a.size()){
        int x=lower_bound(a.begin(),a.end(),a[i]+k)-a.begin();
        if(a[x]!=a[i]+k)
            --x;
        
        ++count;
        int y= lower_bound(a.begin(),a.end(),a[x]+k)-a.begin();
        if(a[y]==a[x]+k)
            ++y;
       
        i=y;
    }
    cout<<count;
    return 0;
}

Approach 3.

#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 i,j,l;
    i=0;
    int count=0;
    while(i<n){
        j=i;
        while((x[j]-x[i])<=k && j<n){
            j++;
        }
        l=j;
        count++;
        while(x[l]-x[j-1]<=k && l<n){
            l++;
        }
        i=l;
    }
    cout<<count<<endl;
    return 0;
}

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe