পাইথনে n বল থেকে k বল বেছে নিয়ে ম্যাক্স-মিন পার্থক্যের যোগফল বের করা

n সংখ্যক বল আছে যাদের নম্বর একটি অ্যারে nums-এ সংরক্ষিত। প্রতিটি টার্নে n বল থেকে k বল বেছে নেওয়া হয় এবং তাদের ম্যাক্সিমাম ও মিনিমাম মানের পার্থক্য একটি টেবিলে সংরক্ষণ করা হয়। তারপর বলগুলো আবার ফেরত দেওয়া হয় এবং এই প্রক্রিয়া সব সম্ভাব্য কোম্বিনেশনের জন্য চলতে থাকে। শেষে টেবিলের সব পার্থক্যের যোগফল বের করতে হবে। উত্তর যদি বড় হয় তবে ১০⁹+৭ দিয়ে মডুলো করুন।

উদাহরণ

ইনপুট: n = 4, k = 3, nums = [5, 7, 9, 11]

আউটপুট: 20

কম্বিনেশনগুলো:

[5,7,9] → পার্থক্য 9-5 = 4
[5,7,11] → পার্থক্য 11-5 = 6
[5,9,11] → পার্থক্য 11-5 = 6
[7,9,11] → পার্থক্য 11-7 = 4

মোট: 4+6+6+4 = 20

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

m := 10⁹ + 7
inv := [0, 1] ইনিশিয়ালাইজ করুন।
i = 2 থেকে n পর্যন্ত:
- inv.append(m - (m // i) * inv[m % i] % m)
comb_count := 1, res := 0
pick = k-1 থেকে n-1 পর্যন্ত:
- res := (res + (nums[pick] - nums[n - 1 - pick]) * comb_count) % m
- comb_count := comb_count * (pick + 1) % m * inv[pick + 2 - k] % m
res রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

def solve(n, k, nums):
    m = 10**9 + 7
    inv = [0, 1]
    for i in range(2, n + 1):
        inv.append(m - m // i * inv[m % i] % m)
    comb_count = 1
    res = 0
    for pick in range(k - 1, n):
        res += (nums[pick] - nums[n - 1 - pick]) * comb_count % m
        res %= m
        comb_count = comb_count * (pick + 1) % m * inv[pick + 2 - k] % m
    return res

# টেস্ট
n = 4
k = 3
nums = [5, 7, 9, 11]
print(solve(n, k, nums))  # আউটপুট: 20

ইনপুট

4, 3, [5, 7, 9, 11]