मध्यम 0 हल किए गए 0% स्वीकृति

Derangements

Count the arrangements of n items where nothing stays in its original place.

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

  • Turn a counting argument into a recurrence
  • Iterate a recurrence from base cases
  • Handle the n = 0 and n = 1 cases

समस्या

अनुवाद दिखाएँ

Five friends put their hats in a pile and each takes one back at random. In how many ways can it happen that nobody gets their own hat? An arrangement of n items in which no item stays in its original position is called a derangement. The counts start 1, 0, 1, 2, 9, 44 and follow D(n) = (n − 1) × (D(n − 1) + D(n − 2)).

Implement derangements(n).

Input

n: The number of items.

Output

Return the number of derangements of n items. D(0) is 1 (the empty arrangement moves nothing that could stay) and D(1) is 0.

सीमाएँ

0 ≤ n ≤ 20

उदाहरण

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

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

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

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

व्याख्या

For items A, B, C only BCA and CAB move every item, so the answer is 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

Start from D(0) = 1 and D(1) = 0.

संकेत 2

Each next value uses the two previous ones and the current n.

संकेत 3

Only the last two values are needed at any time.

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

O(n) time, O(1) extra space

संदर्भ

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

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

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

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

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

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