मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है जो 1-आयामी रेखा पर घरों की स्थिति का प्रतिनिधित्व कर रहे हैं। अब विचार करें कि हमारे पास 3 स्ट्रीट लाइट हैं जिन्हें हम लाइन पर कहीं भी लगा सकते हैं और x स्थिति में एक लाइट [x - r, x + r] सहित सभी घरों को रोशनी देती है। हमें सभी घरों को रोशन करने के लिए आवश्यक सबसे छोटा r खोजना होगा।
इसलिए, यदि इनपुट nums =[4,5,6,7] की तरह है, तो आउटपुट 0.5 होगा, क्योंकि हम लैंप को 4.5, 5.5 और 6.5 पर रख सकते हैं इसलिए r =0.5। तो ये तीनों बत्तियाँ चारों घरों को रोशन कर सकती हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन मान्य() परिभाषित करें। इसमें r लगेगा
-
last_location :=nums[0] + r
-
गिनती :=1
-
मैं के लिए 0 से लेकर अंकों के आकार तक, करें
-
वैल:=अंक [i]
-
अगर वैल - last_location> r, तो
-
गिनती :=गिनती + 1
-
last_location :=वैल + आर
-
-
-
गिनती <=3 होने पर सही लौटें, अन्यथा गलत
-
मुख्य विधि से निम्न कार्य करें -
-
सूची संख्या क्रमित करें
-
बायां :=0
-
दाएं:=अंकों का अंतिम तत्व
-
रेस :=inf
-
आईटीआर:=0
-
जबकि बाएँ <=दाएँ और itr <20, करें
-
मध्य:=बाएँ + (दाएँ - बाएँ) / 2
-
यदि मान्य (मध्य) सत्य है, तो
-
रेस :=न्यूनतम रेस और मध्य
-
दाएं:=मध्य
-
-
अन्यथा,
-
बाएं :=मध्य
-
आईटीआर:=आईटीआर + 1
-
-
-
रिटर्न रेस
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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