मान लीजिए कि हमारे पास n-1 अंकगणितीय अनुक्रम शब्दों को धारण करने वाला nums नामक एक सरणी है। अंकों के पहले या अंतिम तत्व को छोड़कर एक तत्व पहले हटा दिया गया था। हमें हटाया गया नंबर ढूंढना है।
इसलिए, यदि इनपुट अंकों की तरह है =[5, 7, 11, 13], तो आउटपुट 9 होगा क्योंकि, आइटम सूत्र 2i+5 का पालन कर रहे हैं, इसलिए i =2 के लिए यह 2*2 + 5 होगा =9 जो गायब है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
यदि अंकों का आकार 2 के समान है, तो
-
(अंकों में मौजूद सभी तत्वों का योग)/2
. का रिटर्न फ्लोर
-
-
अगर nums[0], nums[1] के समान है, तो/p>
-
वापसी संख्या[0]
-
-
निचला:=अंक [0]
-
ऊपरी:=अंकों का अंतिम तत्व
-
अंतराल:=(ऊपरी-निचले) का तल / अंकों का आकार
-
सूचक :=अंकों के आकार का तल / 2
-
बायां :=0
-
दाएं:=अंकों का आकार - 1
-
जबकि बायां दाएं के समान नहीं है, करें
-
यदि अंक [सूचक] अंक [0] + अंतराल * सूचक के समान नहीं है, तो
-
अगर nums[pointer - 1], nums[0] + इंटरवल *(पॉइंटर -1) के समान है, तो
-
वापसी अंक [0] + अंतराल * सूचक
-
-
अन्यथा,
-
दाएँ:=सूचक
-
सूचक :=तल (बाएं + दाएं) / 2
-
-
-
अन्यथा,
-
यदि दाएँ-बाएँ 1 के समान हैं, तो
-
सूचक :=दाएँ
-
-
अन्यथा,
-
बायां:=सूचक
-
सूचक :=तल (बाएं + दाएं) / 2
-
-
-
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें
def solve(nums):
if len(nums) == 2:
return sum(nums) // 2
if nums[0] == nums[1]:
return nums[0]
lower = nums[0]
upper = nums[-1]
interval = (upper - lower) // len(nums)
pointer = len(nums) // 2
left = 0
right = len(nums) - 1
while left != right:
if nums[pointer] != nums[0] + interval * pointer:
if nums[pointer - 1] == nums[0] + interval * (pointer -1):
return nums[0] + interval * pointer
else:
right = pointer
pointer = (left + right) // 2
else:
if right - left == 1:
pointer = right
else:
left = pointer
pointer = (left + right) // 2
nums = [5, 7, 11, 13]
print(solve(nums)) इनपुट
[5, 7, 11, 13]
आउटपुट
9
