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

একটি অ্যারে nums দেওয়া আছে যেটি n-1 টি আর্থমেটিক সিকোয়েন্স টার্ম ধারণ করে (প্রথম ও শেষ বাদ দিয়ে একটি টার্ম বাদ পড়েছে)। বাদ পড়া সংখ্যা বের করুন।

উদাহরণ

nums = [5, 7, 11, 13] → আউটপুট: 9

সিকোয়েন্স: ২i+5, i=2 → ৯ বাদ।

এলগরিদম (বাইনারি সার্চ)

1. যদি len(nums)==2: রিটার্ন sum(nums)//2
2. যদি nums[0]==nums[1]: রিটার্ন nums[0]
3. lower := nums[0], upper := nums[-1]
4. interval := (upper - lower) // len(nums)
5. বাইনারি সার্চ দিয়ে সঠিক পজিশন খুঁজে বের করুন।

পাইথন কোড

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))  # আউটপুট: 9

ইনপুট / আউটপুট

[5, 7, 11, 13]
9