समस्या
पाँच दोस्त अपनी टोपियाँ एक ढेर में रख देते हैं और फिर हर कोई बिना देखे एक टोपी उठा लेता है। कितने तरीकों से ऐसा हो सकता है कि किसी को भी अपनी टोपी न मिले? 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
उदाहरण
इनपुट:
n = 3
अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long n = 3;
अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long n = 3;
अपेक्षित आउटपुट:
long expected = 2;
व्याख्या
A, B, C के लिए सिर्फ़ BCA और CAB में हर वस्तु अपनी जगह से हटती है, इसलिए उत्तर 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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।