Friends Pairing Problem

Posted: 27 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an integer ‘N’, which denotes there are ‘N’ friends. You are supposed to form some pairs them satisfying the following conditions:

1. Each friend can be paired with some other friend or remain single.

2. Each friend can be a part of at most one pair.

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.
Try Problem