मान लीजिए हमारे पास दो सूचियाँ nums1 और nums2 हैं। अब प्रतिबंध यह है कि जब हम मर्ज करते हैं तो प्रत्येक सूची में तत्वों का क्रम नहीं बदलता, उदाहरण के लिए, यदि तत्व [1,2,3] और [4,5,6] हैं, तो कुछ मान्य मर्ज की गई सूचियाँ [1,4,2,3,5,6] और [1,2,3,4,5,6] हैं, कुछ अन्य मान्य मर्ज अनुक्रम हो सकते हैं। तो यदि हमारे पास सूचियों का आकार N और M है। हमें उन्हें मर्ज करने के तरीकों की संख्या खोजनी है ताकि मान्य सूची प्राप्त हो सके। यदि उत्तर बहुत बड़ा है तो परिणाम मॉड्यूलो 10^9 + 7 लौटाएं।
तो, यदि इनपुट N = 5, M = 3 है, तो आउटपुट 56 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- ret := 1
- i को N + 1 से N + M तक की रेंज में, करें
- ret := ret * i
- i को 1 से M तक की रेंज में, करें
- ret := r/i का फ्लोर
- ret mod (10^9 + 7) लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def solve(N, M): ret = 1 for i in range(N + 1, N + M + 1): ret *= i for i in range(1, M + 1): ret //= i return ret % (10**9 + 7) N = 5 M = 3 print(solve(N, M))
इनपुट
5, 3
आउटपुट
56