सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

डीरेंजमेंट (Derangements)

n वस्तुओं की वे व्यवस्थाएँ गिनिए जिनमें कोई भी वस्तु अपनी मूल जगह पर न रहे।

आप क्या सीखेंगे

  • गिनती के तर्क को पुनरावृत्ति संबंध में बदलना
  • आधार मामलों से शुरू करके पुनरावृत्ति संबंध चलाना
  • n = 0 और n = 1 के मामले संभालना

समस्या

पाँच दोस्त अपनी टोपियाँ एक ढेर में रख देते हैं और फिर हर कोई बिना देखे एक टोपी उठा लेता है। कितने तरीकों से ऐसा हो सकता है कि किसी को भी अपनी टोपी न मिले? n वस्तुओं की ऐसी व्यवस्था, जिसमें कोई भी वस्तु अपनी मूल जगह पर न रहे, डीरेंजमेंट (derangement) कहलाती है। इनकी गिनती 1, 0, 1, 2, 9, 44 से शुरू होती है और D(n) = (n − 1) × (D(n − 1) + D(n − 2)) नियम से आगे बढ़ती है।

derangements(n) लिखिए।

इनपुट

n: वस्तुओं की संख्या।

आउटपुट

n वस्तुओं के डीरेंजमेंट की संख्या लौटाइए। D(0) = 1 है (खाली व्यवस्था में कोई वस्तु ही नहीं जो अपनी जगह पर रह जाए) और D(1) = 0 है।

सीमाएँ

0 ≤ n ≤ 20

उदाहरण

उदाहरण 1
इनपुट:
n = 3

अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long n = 3;

अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long n = 3;

अपेक्षित आउटपुट:
long expected = 2;

व्याख्या

A, B, C के लिए सिर्फ़ BCA और CAB में हर वस्तु अपनी जगह से हटती है, इसलिए उत्तर 2 है।

उदाहरण 2
इनपुट:
n = 4

अपेक्षित आउटपुट:
expected = 9
इनपुट:
long long n = 4;

अपेक्षित आउटपुट:
long long expected = 9;
इनपुट:
long n = 4;

अपेक्षित आउटपुट:
long expected = 9;

व्याख्या

D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

D(0) = 1 और D(1) = 0 से शुरू कीजिए।

संकेत 2

हर अगला मान पिछले दो मानों और मौजूदा n से बनता है।

संकेत 3

किसी भी समय सिर्फ़ आख़िरी दो मानों की ज़रूरत होती है।

अपेक्षित जटिलता

समय O(n), अतिरिक्त स्थान O(1)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।