Friends Pairing Problem

Easy
0/40
Average time to solve is 10m
profile
Contributed by
24 upvotes
Asked in companies
Goldman SachsPayPalHCL Technologies

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
1
Sample Output 1:
4
1
Explanation for Sample Input 1:
In the first test case, there are three friends, and the following pairings can be done:
All single Combination: {1}, {2}, {3}
One pair Combination: {1}, {2, 3} ; {1, 2}, {3} ; {1, 3}, {2}
In the case of zero pairings, nobody is paired with each other. This is one of the possible answers.
In the case of one pair combination, Three answers are possible: the Second is paired with the Third, the First is paired with the Second, and the First is paired with the third.
Here, Two pairs can’t be made as there are only four friends.
So, the answer is 1 + 3 = 4

In the second test case, there is only one friend and can’t be paired with any other. So, the answer is 1.
Sample Input 2:
2   
10
2
Sample Output 2:
9496
2
Hint

Recursively check how many options the nth person has?

Approaches (4)
Bruteforce

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.
Time Complexity

O(2^N), where ‘N’ is the given integer.

 

For each function call, we are making two recursive function calls. So, there will be a total of 2^N function calls. Hence, the overall time complexity is O(2^N). 

Space Complexity

O(N), where ‘N’ is the given integer

 

We are using the recursion stack, which will have a maximum size of ‘N’. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Friends Pairing Problem
Full screen
Console