Write an Algorithm to Help Noddy Find the House Numbers

Minimum number of towers required such that every house is in the range of at least one tower

Given a map of the city and the network range, the task is to determine the minimum number of the tower so that every house is within range of at least one tower. Each tower must be installed on top of an existing house.

Examples:

Try Amazon Test Series that Includes topic-wise practice questions on all important DSA topics along with 10 practice contests of 2 hours each. Designed with years of experience.

Input: range : 1        house : 1 2 3 4 5 Output: 2  Input: range : 2        house : 7 2 4 6 5 9 12 11  Output: 3

All cities can be covered by inserting 2 towers i.e. at house 2 and 4.

All cities can be covered by inserting 3 towers i.e. at house 4, 9, and 12.
Algorithm:-

1. First, sort all the elements.
2. Count only once and then traverse till its middle house.
3. After this again traverse till tower range.
4. Again repeat 1, 2, 3 steps till all the houses are covered.

Below is the implementation of above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int number_of_tower( int house[], int range, int n)

{

sort(house, house + n);

int numOfTower = 0;

int i = 0;

while (i < n) {

numOfTower++;

int loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

--i;

loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

}

return numOfTower;

}

int main()

{

int house[] = { 7, 2, 4, 6, 5, 9, 12, 11 };

int range = 2;

int n = sizeof (house) / sizeof (house[0]);

cout << number_of_tower(house, range, n);

}

Java

import java.util.Arrays;

public class Improve {

static int number_of_tower( int house[], int range, int n)

{

Arrays.sort(house);

int numOfTower = 0 ;

int i = 0 ;

while (i < n) {

numOfTower++;

int loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

--i;

loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

}

return numOfTower;

}

public static void main(String args[])

{

int house[] = { 7 , 2 , 4 , 6 , 5 , 9 , 12 , 11 };

int range = 2 ;

int n = house.length;

System.out.println(number_of_tower(house, range, n));

}

}

Python 3

def number_of_tower(house, r, n):

house.sort()

numOfTower = 0

i = 0

while (i < n) :

numOfTower + = 1

loc = house[i] + r

while (i < n and house[i] < = loc):

i + = 1

i - = 1

loc = house[i] + r

while (i < n and house[i] < = loc):

i + = 1

return numOfTower

if __name__ = = "__main__" :

house = [ 7 , 2 , 4 , 6 , 5 , 9 , 12 , 11 ]

r = 2

n = len (house)

print (number_of_tower(house, r, n))

C#

using System;

public class Improve {

static int number_of_tower( int []house, int range, int n)

{

Array.Sort(house);

int numOfTower = 0;

int i = 0;

while (i < n) {

numOfTower++;

int loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

--i;

loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

}

return numOfTower;

}

public static void Main()

{

int []house = { 7, 2, 4, 6, 5, 9, 12, 11 };

int range = 2;

int n = house.Length;

Console.WriteLine(number_of_tower(house, range, n));

}

}

PHP

<?php

function number_of_tower( $house , $range , $n )

{

sort( $house );

$numOfTower = 0;

$i = 0;

while ( $i < $n ) {

$numOfTower ++;

$loc = $house [ $i ] + $range ;

while ( $i < $n && $house [ $i ] <= $loc )

$i ++;

-- $i ;

$loc = $house [ $i ] + $range ;

while ( $i < $n && $house [ $i ] <= $loc )

$i ++;

}

return $numOfTower ;

}

$house = array ( 7, 2, 4, 6, 5, 9, 12, 11 );

$range = 2;

$n = sizeof( $house ) / sizeof( $house [0]);

echo number_of_tower( $house , $range , $n );

?>

Javascript

<script>

function number_of_tower(house,range,n)

{

house.sort( function (a,b){ return a-b;});

let numOfTower = 0;

let i = 0;

while (i < n) {

numOfTower++;

let loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

--i;

loc = house[i] + range;

while (i < n && house[i] <= loc)

i++;

}

return numOfTower;

}

let house=[7, 2, 4, 6, 5, 9, 12, 11];

let range = 2;

let n = house.length;

document.write(number_of_tower(house, range, n));

</script>

Time Complexity: O(nlogn)
Space Complexity: O(1)

Write an Algorithm to Help Noddy Find the House Numbers

Source: https://www.geeksforgeeks.org/minimum-number-of-towers-required-such-that-every-house-is-in-the-range-of-at-least-one-tower/

Bagikan Artikel ini