N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R?

N is an array containing location of each house. K is an integer value.

I am unable to identify the algo for this. I tried solving by taking location of 1st and last house, then dividing by K, this will give me max range of each streetlight. However, assume N=[3,4,5,10,13] and K=3. With division this wont work.


This is a known problem: https://binarysearch.com/problems/Minimum-Light-Radius

Key Idea: Binary search for the diameter, then use that to find the radius.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.