Hackerland Radio Transmitters- HackerRank | 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.

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

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

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

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

Subtasks

for of the maximum score.

Output Format

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

Explanation 0

The diagram below depicts our map of Hackerland:

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

Sample Input 1

8 2
7 2 4 6 5 9 12 11

Sample Output 1

Explanation 1

The diagram below depicts our map of Hackerland:

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

#include<stdio.h>

void merge(int arr[], int l, int m, int r)
{
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;

	int L[n1], R[n2];

	for (i = 0; i < n1; i++)
		L[i] = arr[l + i];
	for (j = 0; j < n2; j++)
		R[j] = arr[m + 1+ j];

	i = 0; 
	j = 0; 
	k = l; 
	while (i < n1 && j < n2)
	{
		if (L[i] <= R[j])
		{
			arr[k] = L[i];
			i++;
		}
		else
		{
			arr[k] = R[j];
			j++;
		}
		k++;
	}


	while (i < n1)
	{
		arr[k] = L[i];
		i++;
		k++;
	}

	while (j < n2)
	{
		arr[k] = R[j];
		j++;
		k++;
	}
}


void mergeSort(int arr[], int l, int r)
{
	if (l < r)
	{
	
		int m = l+(r-l)/2;


		mergeSort(arr, l, m);
		mergeSort(arr, m+1, r);

		merge(arr, l, m, r);
	}
}



int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int x[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x[i]);
    }
    mergeSort(x, 0, n- 1);

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

    printf("%d",numOfTransmitters);
    return 0;
}

Hackerland Radio Transmitters- HackerRank | Solution

Table of Contents