Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में n गेंदों से यादृच्छिक रूप से चुनी गई k गेंदों के अधिकतम और न्यूनतम तत्वों के बीच अंतर के योग का प्रोग्राम


मान लीजिए हमारे पास 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

  1. पायथन में नोड और उसके वंशज के बीच अंतर खोजने का प्रोग्राम पायथन में नोड और उसके वंशज के बीच अंतर खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें किसी भी नोड और उसके वंशजों के बीच सबसे बड़ा निरपेक्ष अंतर ढूंढना है।उदाहरण के लिए, यदि इनपुट ट्री है:तो आउटपुट 7 होगा क्योंकि सबसे बड़ा निरपेक्ष अंतर नोड्स 8 और 1 के बीच है।समाधान दृष्टिकोणइसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (पोस्ट-ऑर्डर

  1. Python में ट्री के सभी एलिमेंट का योग खोजने का प्रोग्राम Python में ट्री के सभी एलिमेंट का योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास कुछ मानों वाला एक बाइनरी ट्री है, हमें ट्री में सभी मानों का योग ढूंढना है। तो, यदि इनपुट इस तरह है तो आउटपुट 14 होगा। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे: recurse() फ़ंक्शन परिभाषित करें। यह node लेगा val := node का मान यदि node का बाएं null नहीं है, तो val := va

  1. पायथन प्रोग्राम: लिस्ट में एलिमेंट्स का योग ढूंढें पायथन प्रोग्राम: लिस्ट में एलिमेंट्स का योग ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट इनपुट के रूप में एक लिस्ट दिए जाने पर, हमें दी गई लिस्ट का योग निकालने की आवश्यकता है। यहां हमारे पास दो दृष्टिकोण हैं: बिल्ट-इन फंक्शन का उपयोग करना और ब्रूट-फोर्स दृष्टिकोण का उपयोग