Minimum number of towers required such that every house is in the range of at least one tower | C ++ implementation of above approach ; Function to count the number of tower ; first we sort the house numbers ; for count number of towers ; for iterate all houses ; count number of towers ; find find the middle location ; traverse till middle location ; this is point to middle house where we insert the tower ; now find the last location ; traverse till last house of the range ; return the number of tower ; Driver code ; given elements ; print number of towers
#include <bits/stdc++.h> NEW_LINE 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 ) ; }