समस्या
एक सामान्य पासा 1 से 6 तक का पूर्णांक उत्पन्न करता है। उन सभी गैर-रिक्त क्रमबद्ध अनुक्रमणिकाओं की गिनती करें जिनका योग target है। अलग-अलग क्रम अलग माने जाएंगे। उत्तर को 1,000,000,007 से मॉड्यूलो लेकर लौटाएँ।
dice_combinations(target) को लागू करें।
इनपुट
target: सभी फेंकों का आवश्यक योग।
आउटपुट
अनुक्रमणिकाओं की संख्या 1,000,000,007 से मॉड्यूलो लेकर लौटाएँ।
सीमाएँ
1 ≤ target ≤ 1,000,000। किसी संख्या को 1,000,000,007 से मॉड्यूलो लेना मतलब है उसे उस संख्या से भाग देने के बाद शेषफल लौटाना।
उदाहरण
इनपुट:
target = 2
अपेक्षित आउटपुट:
expected = 2इनपुट:
long long target = 2;
अपेक्षित आउटपुट:
long long expected = 2;इनपुट:
long target = 2;
अपेक्षित आउटपुट:
long expected = 2;व्याख्या
दो अनुक्रमणिकाएँ हैं: [2] और [1, 1]।
इनपुट:
target = 4
अपेक्षित आउटपुट:
expected = 8इनपुट:
long long target = 4;
अपेक्षित आउटपुट:
long long expected = 8;इनपुट:
long target = 4;
अपेक्षित आउटपुट:
long expected = 8;व्याख्या
अनुक्रमणिकाएँ हैं: [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1], और [1,1,1,1]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
छोटे sums को target बनाने के लिए building blocks की तरह सोचो.
संकेत 2
हर sum का running count पिछले छह sums पर आधारित रखो.
संकेत 3
हर addition पर modulo लगाना मत भूलो, और 1 से छोटे sums को separately handle करो.
अपेक्षित जटिलता
समय O(target), अतिरिक्त स्थान O(target)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।