Problem Code- CN03
Difficulty: Medium
Prerequisites:
Binary Search
Explanation:
With the problem rephrased to fit our needs better, we can now examine the predicate //Check predicate ‘Can the minimum distance be x with no. of wifi given ?’. This concludes the first part of building a binary search solution, we now just have to prove that the condition in the main theorem is satisfied. But observe that increasing x actually relaxes the limit , so we can only need the same number of wifi or fewer, not more. Thus, if the predicate says yes for some x, it will also say yes for all larger x.
Here’s an STL driven approach:
ll Wifi(vector v,ll wifi)
{
ll n = v.size();
ll hi= v[n-1];
ll lo= 1;
while(lo<hi)
{
ll x = lo + (hi-lo+1)/2;
//Check predicate 'Can the minimum distance be x with no. of wifi given ?'
ll required_wifi=1, current=v[0];
for(ll i=1;i<n;i++)
{
if(v[i]-current>=x)
{
++required_wifi;
current=v[i];
}
else
{
}
}
//check if predicate is true or false
if(required_wifi<wifi) //false
hi=x-1;
else //true
lo= x;
}
return lo;
}