# Friends Pairing Problem

Posted: 27 Feb, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### You are supposed to find the total number of ways in which the pairing can be done satisfying both conditions. Since the number of ways can be quite large, you should find the answer modulo 1000000007(10^9+7).

##### Note:
``````1. Return the final answer by doing a mod with 10^9 + 7.
2. Pairs {A, B} and {B, A} are considered the same.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains one integer, ‘N’, denoting the number of friends.
``````
##### Output Format:
``````For each test case, return the total number of ways in which the pairing can be done.
``````
##### Constraints:
``````1<= T <= 100
1 <= N <= 10^4

Time Limit: 1 sec
`````` Approach 1

The idea is to solve the problem using recursion and break down the problem into different subproblems.

Let’s define NUMBER_OF_WAYS(N) as the total number of ways ‘N’ friends can be paired up or remain single.

The N-th person has two choices - either remain single or pair up with one of the other ‘N - 1’ friends.

If he remains single, then the number of possible pairings are NUMBER_OF_WAYS(N - 1) as there are (N - 1) more friends to be paired up or stay single.

If he pairs up, he can pair with any one of the (N - 1) friends, and there are (N - 2) friends to be paired up or remain single. Hence, by the rule of product, the number of possible pairings, in this case, will be (N-1)*NUMBER_OF_WAYS(N-2).

So, the recurrence relation can be written as :

NUMBER_OF_WAYS(N) = NUMBER_OF_WAYS(N - 1) + (N - 1)*NUMBER_OF_WAYS( N - 2)

• Base Condition: If N is less than 3, then return N.
• Otherwise, return NUMBER_OF_WAYS(N) = NUMBER_OF_WAYS(N - 1) + (N - 1)*NUMBER_OF_WAYS( N - 2)
• We will perform all operations under the given modulo to prevent overflow.