Home » Interview coding problems/challenges

Friends pairing problem

Friends pairing problem: Here, we are going to learn about the Friends pairing problem and its solution which is used to find the number of ways of pairing between N friends using dynamic programming. Submitted by Radib Kar, on December 27, 2019

This is a standard interview problem to find the number of ways of pairing between N friends using dynamic programming.

Problem statement

There are N friends, each one of them can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways to do so. Since inputs are big return answer MOD 10^9+7.

    Input:
    Test case t
    t no of lines with value of N
    e.g.
    3
    5
    4

    1<=t<=100
    1<=N<=100

    Output:
    t number of lines

Example

    Input:   t=3, n=3
    Output:  4

    Input:   n=4
    Output:  10

    Input:   n=5
    Output:  26

Explanation with example

Let there are N number of friends, say x₁, x₂, ..., x_n

Now, possible orderings can be:

1. All are single. {x₁, x₂, ... , x_n}
2. x₁ is single , others are paired contiguously(if n is odd). {x₁, (x₂, x₃), ...}
   So on. So if we try to figure out a formula then to observe that.
   For any x_i
   1. x_i can be kept single
   2. x_i can be paired with any other x_j provided i≠j

Let f(n)= number of ways to pair for input N

Considering the above two facts about x_i

If x_n is kept single then f(n) = f(n-1) (same as number of ways excluding x_n)
If x_n is paired with any other friend then f(n)=(n-1)*f(n-2) (number of ways xn can be paired * sub-problem excluding x_n and the paired one with it)

So the recursion function to solve the problem:

    f(n)=f(n-1)+(n-1)*f(n-2)

    For n=4
    Friends are {1, 2, 3, 4}

    So the pairings can be are:
    {1, 2, 3, 4}
    {1, 2, (3, 4)}
    {1, (2, 3), 4}
    {(1, 4), 2, 3}
    {(1, 3), 2, 4}
    {(2, 4), 1, 3}
    {(1, 2), 3, 4}
    {(1, 2), (3, 4)}
    {(1, 3), (2, 4)}
    {(1, 4), (2, 3)}
    
    So total 10 possible type of pairings, hence output is 10

    So the recursion tree for the above would be:
    

    
    

We see that we are evaluating many sub-problem several times. Like f(2) has been evaluated more than one time and the same also for others. It’s easily understandable that for such small input there are so many repeated computations, then for higher inputs, how many overlapping there will be. Here comes the need for DP, where we can use tabulation to solve bigger subproblems using smaller ones.

Problem Solution:

Recursive Algorithm:

    Function(n):
        If n==0 or n==1 
            Return 1
        Else
            Return Function(n-1)+(n-1)*Function(n-2); 

Conversion to DP:

    For tabulation we need arr[n+1] to store
        arr[0]=1
        arr[1]=1
    To fill the higher values,
        for i=2 to n
            arr[i]=arr[i-1]+(i-1)*arr[i+1]
        End for

To avoid Time Limit Exceed:

Since there are multiple test cases, we may get TLE even after using DP. To avoid that best way is to pre-compute the table up to input constraint. According to our example,

    1<=N<=100

So better pre-compute arr[101] and return O(1) in time executing the test case query. No need to construct the table again and again for each test case.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

#define N 100
#define MOD 1000000007
long long int arr[N + 1] = { 0 }; //DP Table

int main()
{
    arr[0] = 1; //f(0)=1
    arr[1] = 1; //f(1)=1

    //pre-compute the table
    for (int i = 2; i <= N; i++) {
        arr[i] = (arr[i - 1] % MOD + ((i - 1) * arr[i - 2]) % MOD) % MOD;
    }

    int t, n;

    cout << "Enter number of test cases: ";
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "Enter number of friends: ";
        cin >> n;
        //just executing query from pre-computed values
        cout << "Answer: " << arr[n] << endl;
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter number of friends: 4
Answer: 10
Enter number of friends: 5
Answer: 26
Enter number of friends: 3
Answer: 4