Friends Pairing 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

Question

Friends Pairing 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

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(2^n)Explanation:

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).

Accepted Answer

Dynamic Programming - Memoization

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.

Space Complexity: O(n)Explanation:

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

We are using a dp array of length ‘N’ to store the results of the subproblems, and the recursion stack will have a maximum size of ‘N’. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

We will calculate the total number of ways in which ‘N’ friends can be paired up or remain single for all values from 1 to ‘N’ at most once. Hence, the time complexity is O(N).

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is given integer.
*/

import java.util.Arrays;
public class Solution {
    public static int countWays(int numberOfFriends,int[] dp)
    {
        // Check if the answer is already calculated before.
        if (dp[numberOfFriends] != -1)
        {
            return dp[numberOfFriends];
        }

        int mod = 1000000007;

        // Base Conditions.
        if (numberOfFriends == 1 || numberOfFriends == 2)
        {
            dp[numberOfFriends] = numberOfFriends;

            return dp[numberOfFriends];
        }

        // Calculating using the recursive formula.
        dp[numberOfFriends] = (int)(countWays(numberOfFriends - 1, dp) + (1l * (numberOfFriends - 1) * (countWays(numberOfFriends - 2, dp))) % mod) % mod;

        return dp[numberOfFriends];
    }

    public static int numberOfWays(int n) {
        // To store answers for the subproblems.
        int[] dp = new int[n+1];
        Arrays.fill(dp, -1);

        return countWays(n, dp);
    }
}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    where 'N' is given integer.

'''



def countWays(numberOfFriends, dp):



    # Check if the answer is already calculated before.

    if (dp[numberOfFriends] != -1):

        return dp[numberOfFriends]



    mod = 1e9 + 7



    # Base Conditions.

    if (numberOfFriends == 1 or numberOfFriends == 2):

        return numberOfFriends



    # Calculating using the recursive formula.

    dp[numberOfFriends] = (countWays(numberOfFriends - 1, dp) + ((numberOfFriends - 1) * countWays(numberOfFriends - 2, dp)) % mod) % mod



    return dp[numberOfFriends]





def numberOfWays(n):



    # To store answers for the subproblems.

    dp = [-1 for i in range(n + 1)]



    return int(countWays(n, dp))

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is given integer.
*/

int countWays(int numberOfFriends, vector &dp)
{
    // Check if the answer is already calculated before.
    if (dp[numberOfFriends] != -1)
    {
        return dp[numberOfFriends];
    }

    int mod = 1e9 + 7;

    // Base Conditions.
    if (numberOfFriends == 1 || numberOfFriends == 2)
    {
        dp[numberOfFriends] = numberOfFriends;

        return dp[numberOfFriends];
    }

    // Calculating using the recursive formula.
    dp[numberOfFriends] = (countWays(numberOfFriends - 1, dp) + (1LL * (numberOfFriends - 1) * (countWays(numberOfFriends - 2, dp))) % mod) % mod;

    return dp[numberOfFriends];
}

int numberOfWays(int N)
{
    // To store answers for the subproblems.
    vector dp(N + 1, -1);

    return countWays(N, dp);
}

Accepted Answer

Dynamic Programming - Tabulation

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':
1. 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].
2. 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].
3. 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.

Space Complexity: O(n)Explanation:

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

We are using a ‘DP’ array of length ‘N’ to store the results of the subproblems, which will have a maximum size of ‘N’. Hence, the overall space complexity of O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the input integer.

We are iterating from 3 to ‘N’, which will take O(N) time. Hence, the overall time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    where 'N' is given integer.

*/

    

public class Solution {

    public static int numberOfWays(int n) {

        // Base Conditions.

		if (n == 1 || n == 2)

		{

			return n;

		}



		// For storing answers to the subproblems.

		int[] dp = new int[n + 1];

		dp[0] = 0;

		dp[1] = 1;

		dp[2] = 2;



		int mod = 1000000007;



		// Iterating and calculating for every value of i = 3 to n.

		for (int i = 3; i <= n; i++)

		{

			dp[i] = (int)(dp[i - 1] + (1l * (i - 1) * (dp[i - 2] % mod)) % mod) % mod;

		}



		return dp[n];

    }

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    where 'N' is given integer.

'''



def numberOfWays(n):



    # Base Conditions.

    if (n == 1 or n == 2):

        return n



    # For storing answers to the subproblems.

    dp = [0 for i in range(n + 1)]



    dp[1] = 1

    dp[2] = 2



    mod = 1e9 + 7



    # Iterating and calculating for every value of i = 3 to N.

    for i in range(3, n + 1):



        dp[i] = (dp[i - 1] + ((i - 1) * dp[i - 2]) % mod) % mod



    return int(dp[n])

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is given integer.
*/

int numberOfWays(int n)
{
	// Base Conditions.
	if (n == 1 || n == 2)
	{
		return n;
	}

	// For storing answers to the subproblems.
	vector dp(n + 1);
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;

	int mod = 1e9 + 7;

	// Iterating and calculating for every value of i = 3 to n.
	for (int i = 3; i <= n; i++)
	{
		dp[i] = (dp[i - 1] + (1LL * (i - 1) * (dp[i - 2] % mod)) % mod) % mod;
	}

	return dp[n];
}

Accepted Answer

Dynamic Programming - Space Optimized

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':
1. Update CURRENT_ANSWER as LAST_SECOND_ANSWER + (i-1) * LAST_SECOND_ANSWER, this is similar to the previous approach.
2. 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.

Space Complexity: O(1)Explanation:

O(1),

As we are using constant extra space.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the input integer.

We are iterating from ‘i’ = 3 to ‘N’, which will take O(N) time. Hence, the overall time complexity is O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    where 'N' is given integer.

'''



def numberOfWays(n):



    # Base Conditions.

    if (n == 1 or n == 2):

        return n



    mod = 1e9 + 7



    # Total number of ways for N = 1 and N = 2 respectively.

    lastSecondAnswer, lastAnswer = 1, 2



    currentAnswer = 0



    # Iterating and calculating for every value of i = 3 to N.

    for i in range(3, n + 1):



        currentAnswer = (lastAnswer + ((i - 1) * lastSecondAnswer) % mod) % mod

        lastSecondAnswer = lastAnswer

        lastAnswer = currentAnswer

    

    return int(currentAnswer)

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    where 'N' is given integer.
*/

public class Solution {
    public static int numberOfWays(int n) {
        // Base Conditions.
		if (n == 1 || n == 2)
		{
			return n;
		}

		int mod = 1000000007;

		// total number of ways for n = 1 and n = 2 respectively.
		int lastSecondAnswer = 1, lastAnswer = 2;

		int currentAnswer = 0;

		// Iterating and calculating for every value of i = 3 to n.
		for (int i = 3; i <= n; i++)
		{
			currentAnswer = (int)(lastAnswer % mod + (1l * (i - 1) * lastSecondAnswer) % mod) % mod;
			lastSecondAnswer = lastAnswer;
			lastAnswer = currentAnswer;
		}

		return currentAnswer;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    where 'N' is given integer.
*/

int numberOfWays(int n)
{
	// Base Conditions.
	if (n == 1 || n == 2)
	{
		return n;
	}

	int mod = 1e9 + 7;

	// total number of ways for n = 1 and n = 2 respectively.
	int lastSecondAnswer = 1, lastAnswer = 2;

	int currentAnswer;

	// Iterating and calculating for every value of i = 3 to n.
	for (int i = 3; i <= n; i++)
	{
		currentAnswer = (lastAnswer % mod + (1l * (i - 1) * lastSecondAnswer) % mod) % mod;
		lastSecondAnswer = lastAnswer;
		lastAnswer = currentAnswer;
	}

	return currentAnswer;
}

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:

Input Format:

Output Format:

Constraints:

Top PayPal Full Stack Developer interview questions & answers

Popular interview questions of Full Stack Developer