Algorithms · Hacker rank

HackerRank ‘ Hackerland Radio Transmitters ‘ Solution

Hackerland is a one-dimensional city with houses, where each house i is located at some  xi on the x-axis. The Mayor wants to install radio transmitters on the roofs of the city’s houses. Each transmitter has a range,k , meaning it can transmit a signal to all houses <=k  units of distance away.

Given a map of Hackerland and the value of , can you find and print the minimum number of transmitters needed to cover every house in the city? (Every house must be covered by at least one transmitter) Each transmitter must be installed on top of an existing house.

Input Format

The first line contains two space-separated integers describing the respective values of (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 (i.e., ).

 

Output Format

Print a single integer denoting the minimum number of transmitters needed to cover all 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 2 and 4. Thus, we print 2 on a new line.

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 4,9 and 12. Thus, we print  3 on a new line.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s