The Book Exchange Ceremony

Moderate

0/80

0 upvote

Asked in company

Problem statement

In a grand ceremony, 'N' scholars, each holding a unique book, are to exchange their books among themselves.

A valid exchange is a permutation of books where any scholar is part of an exchange cycle of at most length 3. This means a scholar can either:

1) Keep their own book (a cycle of length 1). 2) Swap books with one other scholar (a cycle of length 2). 3) Participate in a three-way exchange (a cycle of length 3).

Your task is to find the total number of distinct, valid book exchange arrangements possible for 'N' scholars. Since the number can be very large, you must return the result modulo 1,000,000,007.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

A single line containing an integer 'N'.

Output Format:

Print a single integer representing the total number of valid arrangements modulo 1,000,000,007.

Note:

This problem can be solved using a recurrence relation (Dynamic Programming).
Let dp[i] be the number of valid arrangements for i scholars. We can form the arrangement for i scholars by considering the i-th scholar:
  1) Case 1: The i-th scholar keeps their own book (1-cycle). The remaining i-1 scholars can be arranged in dp[i-1] ways.
  2) Case 2: The i-th scholar swaps with one of the i-1 other scholars (2-cycle). There are i-1 choices for the swap partner. The remaining i-2 scholars can be arranged in dp[i-2] ways.
  3) Case 3: The i-th scholar joins a 3-cycle with two of the i-1 other scholars. There are (i-1) * (i-2) ways to choose two other scholars in a specific order for a 3-cycle. The remaining i-3 scholars can be arranged in dp[i-3] ways.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

With 2 scholars (1, 2), there are two valid arrangements:
1.  Both keep their own books: (1)(2).
2.  They swap books: (1 2).
Total is 2.

Sample Input 2:

Sample Output 2:

Explanation for Sample 2:

With 3 scholars (1, 2, 3), all possible permutations are valid as they only contain cycles of length 1, 2, or 3.
- 1-cycles only: (1)(2)(3)
- One 2-cycle: (1 2)(3), (1 3)(2), (2 3)(1)
- One 3-cycle: (1 2 3), (1 3 2)
Total arrangements = 1 + 3 + 2 = 6.

Expected Time Complexity:

The expected time complexity is O(n).

Constraints:

1 <= N <= 10^6

Time limit: 1 sec

Approaches (1)

Approach 1

The Book Exchange Ceremony

Time Complexity

The expected time complexity is O(n).

Space Complexity

(100% EXP penalty)

The Book Exchange Ceremony

Console