পাইথনে স্ট্রিট লাইট দিয়ে সব বাড়ি আলোকিত করার ন্যূনতম ত্রিজ্যা বের করার প্রোগ্রাম

ধরুন nums একটি লিস্ট যেটি ১-ডাইমেনশনাল লাইনে বাড়ি গুলোর পজিশন নির্দেশ করে। আমাদের ৩টি স্ট্রিট লাইট আছে যেগুলো লাইনের যেকোনো জায়গায় রাখা যায়। একটি লাইট যদি পজিশন x-এ থাকে তবে সেটি [x-r, x+r] রেঞ্জের সব বাড়ি আলোকিত করে। সব বাড়ি আলোকিত করতে ন্যূনতম r বের করতে হবে।

উদাহরণস্বরূপ, nums = [4,5,6,7] হলে আউটপুট হবে 0.5, কারণ ল্যাম্পগুলো 4.5, 5.5, 6.5-এ রাখলে r = 0.5-এ সব ৪টি বাড়ি আলোকিত হয়।

সমাধানের ধাপসমূহ

valid() ফাংশন ডিফাইন করুন যা r নেয়
last_location := nums[0] + r
count := 1
i = 0 থেকে nums-এর আকার-১ পর্যন্ত লুপ:
- val := nums[i]
- যদি val - last_location > r হয়:
  - count := count + 1
  - last_location := val + r
count <= 3 হলে True রিটার্ন করুন, অন্যথায় False
মূল মেথড থেকে:
- nums সর্ট করুন
- left := 0, right := nums[-1], res := inf, itr := 0
- while left <= right এবং itr < 20:
  - mid := left + (right - left) / 2
  - যদি valid(mid) true হয়:
    - res := min(res, mid)
    - right := mid
  - অন্যথায়:
    - left := mid
    - itr := itr + 1
- res রিটার্ন করুন

উদাহরণ

class Solution:
    def solve(self, nums):
        def valid(r):
            last_location = nums[0] + r
            count = 1
            for i in range(len(nums)):
                val = nums[i]
                if val - last_location > r:
                    count += 1
                    last_location = val + r
            return count <= 3
        nums.sort()
        left = 0
        right = nums[-1]
        res = float("inf")
        itr = 0
        while left <= right and itr < 20:
            mid = left + (right - left) / 2
            if valid(mid):
                res = min(res, mid)
                right = mid
            else:
                left = mid
            itr += 1
        return res

ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums))

ইনপুট

[4,5,6,7]

আউটপুট

0.5