পাইথনে n বল থেকে এলোমেলোভাবে নির্বাচিত k বল থেকে সর্বাধিক এবং সর্বনিম্ন উপাদানগুলির মধ্যে পার্থক্যের যোগফল খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে n বল আছে যেগুলিকে একটি অ্যারে সংখ্যা দ্বারা সংখ্যা করা হয়েছে, যার আকার n এবং nums[i] বলের সংখ্যাকে প্রতিনিধিত্ব করে। এখন আমাদের আরেকটি মান k আছে। প্রতিটি পালা আমরা n বিভিন্ন বল থেকে k বল বাছাই করি এবং k বলের সর্বোচ্চ এবং সর্বনিম্ন মানের পার্থক্য খুঁজে পাই এবং পার্থক্যটি একটি টেবিলে সংরক্ষণ করি। তারপর এই k বলগুলিকে আবার সেই পাত্রে রাখুন এবং যতক্ষণ না আমরা সমস্ত সম্ভাব্য নির্বাচন নির্বাচন করি ততক্ষণ আবার বাছাই করুন। অবশেষে টেবিল থেকে সমস্ত পার্থক্যের যোগফল বের করুন। যদি উত্তরটি খুব বড় হয়, তাহলে ফলাফল মোড 10^9+7 ফেরত দিন।

সুতরাং, যদি ইনপুট 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^9 + 7
inv :=উপাদানগুলি সহ একটি নতুন তালিকা [0, 1]
2 থেকে n রেঞ্জের i জন্য, করুন
- ইনসার্ট (m - ফ্লোর অফ (m / i) * inv[m mod i] mod m) inv এর শেষে
comb_count :=1
res :=0

res :=res +(nums[pick] - nums[n - 1 - pick]) * comb_count mod m
res :=res mod m
comb_count :=comb_count *(pick + 1) mod m * inv[pick + 2 - k] mod m

রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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))

ইনপুট

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