পাইথনে নির্দিষ্ট ক liczbা লম্পatë এ শেষ দ্বীপে পৌঁছানোর জন্য ন্যূনতম সর্বোচ্চ লম্পাট দৈর্ঘ্য

একটি অ্যারে A দেওয়া আছে যেখানে A[i] হলো i-তম দ্বীপের অবস্থান। আরেকটি পূর্ণসংখ্যা k দেওয়া আছে (1 ≤ k < N)। একজন ব্যক্তি ০-তম দ্বীপ থেকে শুরু করে ঠিক k সংখ্যক লম্পাট দিয়ে শেষ দ্বীপে পৌঁছাতে হবে। লক্ষ্য হলো সবচেয়ে বড় লম্পাটের দৈর্ঘ্য ন্যূনতম করা। দ্বীপগুলোর অবস্থান ক্রমবর্ধমান ক্রমে দেওয়া থাকে।

উদাহরণ

ইনপুট: A = [7, 20, 41, 48], k = 2

আউটপুট: 28

ব্যাখ্যা: দুটি পথ সম্ভব — 7→20→48 (সর্বোচ্চ লম্পাট 28) এবং 7→41→48 (সর্বোচ্চ লম্পাট 34)। ন্যূনতম হলো 28।

সমাধানের পদ্ধতি

বাইনারি সার্চ (Binary Search) ব্যবহার করে উত্তর খুঁজে বের করা হয়।
`isPossible(arr, dist, k)` ফাংশন চেক করে যে দেয়া `dist` এর মধ্যে `k` বা তার কম লম্পাটে শেষে পৌঁছানো সম্ভব কিনা।
বাইনারি সার্চের লো (low) = ০ এবং হাই (high) = শেষ দ্বীপের অবস্থান।
মিড (mid) দিয়ে চেক করা হয়, সম্ভব হলে হাই কমানো হয়, না হলে লো বাড়ানো হয়।

পাইথন কোড

def isPossible(arr, dist, k):
    n = len(arr)
    req = 0
    current = 0
    previous = 0
    
    for i in range(n):
        while current != n and (arr[current] - arr[previous]) <= dist:
            current += 1
        req += 1
        if current == n:
            break
        previous = current - 1
    
    if current != n:
        return False
    if req <= k:
        return True
    return False

def minimum_distance(arr, k):
    n = len(arr)
    left = 0
    right = arr[-1]
    ans = 0
    
    while left <= right:
        mid = (left + right) // 2
        if isPossible(arr, mid, k):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

arr = [7, 20, 41, 48]
k = 2
print(minimum_distance(arr, k))

ইনপুট

[7, 20, 41, 48], 2