मान लीजिए हमारे पास n गेंदें हैं जिन्हें एक सरणी nums द्वारा संख्या दी गई है, जिसका आकार n है और nums[i] गेंद 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] वाली एक नई सूची
- i को 2 से n तक की रेंज में, करें
- (m - floor of (m / i) * inv[m mod i] mod m) को inv के अंत में डालें
- comb_count := 1
- res := 0
- pick को k - 1 से n - 1 तक की रेंज में, करें
- 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
- 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))
इनपुट
4, 3, [5, 7, 9, 11]
आउटपुट
20