मान लीजिए हमारे पास nums नामक एक ऐरे है जिसमें n-1 अंकगणितीय अनुक्रम पद हैं। nums के पहले या अंतिम तत्व को छोड़कर एक तत्व पहले हटा दिया गया था। हमें हटाई गई संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट है nums = [5, 7, 11, 13], तो आउटपुट होगा 9 क्योंकि, आइटम फॉर्मूला 2i+5 का पालन करते हैं, तो i = 2 के लिए यह 2*2 + 5 = 9 होगा जो गायब है।
समाधान दृष्टिकोण
कॉमन डिफरेंस interval = (last - first) // n की गणना करें। फिर बाइनरी सर्च का उपयोग करके उस इंडेक्स को ढूंढें जहां nums[i] != first + interval * i। गायब मान first + interval * i है।
- यदि लंबाई 2 है, तो औसत लौटाएं।
- यदि पहले दो तत्व समान हैं, तो उस मान को लौटाएं।
interval = (upper - lower) // len(nums)की गणना करें।- बाइनरी सर्च का उपयोग करके विचलन ढूंढें: यदि
nums[mid] != lower + interval * mid, तो जांचें कि क्या पिछला सही है (गायब मिला) अन्यथा बाएं खोजें। - अन्यथा दाएं खोजें।
पायथन कार्यान्वयन
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