Last Updated: 27 Feb, 2021
Friends Pairing Problem
Easy
Asked in companies
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
Approaches
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.
On observing the recursion tree for the previous problem, we can see that we are solving a subproblem multiple times, i.e., for some ‘X’ we are calculating the value of NO_OF_WAYS(X) multiple times.
The idea here is similar to the previous approach. But in this approach, we will be avoiding repeated recursion calls for a subproblem by storing the results for the subproblems.
The idea is to store the answer of the current recursive call in an array and then return the answer.
This approach is called Memoization.
The steps are as follows:
- Initialize a vector ‘DP’ of size ‘N+1’ with -1 in all the indices, which will store the answers for the subproblems. Here, DP[i] will store the number of ways to pair up ‘i’ friends.
- Define a function ‘COUNT_WAYS’, which takes two arguments, NUMBER_OF_FRIENDS and an array ‘DP’, where NUMBER_OF_FRIENDS denotes the number of friends and ‘DP’ is the array used for storing the results of subproblems.
- Check if the value of ‘NUMBER_OF_FRIENDS’ for the current function call is already computed or not.
- If it is already computed, i.e. DP[NUMBER_OF_FRIENDS] != -1 , then return that answer.
- If not, check the base conditions, i.e., If ‘NUMBER_OF_FRIENDS’ is less than 3, then return ‘NUMBER_OF_FRIENDS’.
- Calculate DP[NUMBER_OF_FRIENDS] = COUNT_WAYS(NUMBER_OF_FRIENDS - 1) + (NUMBR_OF_FRIENDS - 1)*COUNT_WAYS(NUMBER_OF_FRIENDS - 2)
- Return DP[NUMBER_OF_FRIENDS]
- We will perform all operations under the given modulo to prevent overflow.
The idea here is to solve the problem iteratively and store the results in an array.
This approach is called Tabulation. In this approach, we compute all the answers starting from ‘i’ = 1 to 'N’, i.e., we check the total number of ways we can pair if 'N’ = 1, then 'N' = 2,......'N' = 'N'.
- Check the base condition, i.e., If 'N' is less than 3, then return 'N'.
- Make a ‘DP’ array of size 'N'+1. Here, DP[i] will store the number of ways to pair up ‘i’ friends.
- Fill the values of base conditions in the ‘DP’ array i.e.DP[1]=1, DP[2]=2.
- Iterate from ‘i’ = 3 to 'N':
- If we decide to keep the i’th friend single, then the number of ways to pair up the remaining ‘i’-1 friends will be given by DP[i-1].
- If we decide to pair up the i’th friend, we have ‘i’-1 friends with whom we can form a pair. After pairing up the i’th friend, we will have ‘i’-2 friends remaining, the number of ways to pair up ‘i’-2 friends will be given by DP[i-2]. Hence, the total number of ways will be (i-1)*DP[i-2].
- Thus the total number of ways to pair up i friends is will be DP[i] = DP[i-1] + ('N'-1) * DP[i-2].
- Return the final answer, i.e., DP['N'].
- We will perform all operations under the given modulo to prevent overflow.
Here, we can observe that calculating for the current subproblem,NO_OF_WAYS (N), only the last answer, i.e., NO_OF_WAYS(N-1), and the second last answer, i.e., NO_OF_WAYS(N-2), is used.
We can also use two variables to store both the answers.
- Check the base conditions, i.e., If 'N' is less than 3, then return 'N'.
- Initialize three integers 'LAST_ANSWER' ,'LAST_SECOND_ANSWER' and 'CURRENT_ANSWER', which stores the last computed, second last computed, and current value respectively, i.e., if we currently at index ‘i’, then 'LAST_ANSWER' stores the computed value at index ‘i’-1 ,'LAST_SECOND_ANSWER' stores the computed value at index ‘i’-2 ,'CURRENT_ANSWER' stores the computed value at index ‘i’ respectively.
- Iterate from ‘i’ = 3 to 'N':
- Update CURRENT_ANSWER as LAST_SECOND_ANSWER + (i-1) * LAST_SECOND_ANSWER, this is similar to the previous approach.
- Update LAST_SECOND_ANSWER to LAST_SECOND_ANSWER and LAST_ANSWER to CURRENT_ANSWER. This step is to change the value of LAST_SECOND_ANSWER and LAST_ANSWER as we are iterating forwards.
- Return the ‘CURRENT_ANSWER’.
- We will perform all operations under the given modulo to prevent overflow.
Similar problems