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 casettno of lines with value ofNe.g. 3 5 4 1<=t<=100 1<=N<=100Output:tnumber of lines

**Example:**

Input:t=3, n=3Output:4Input:n=4Output:10Input:n=5Output:26

**Explanation with example:**

Let there are N number of friends, say x_{1}, x_{2}, ..., x_{n}

Now, possible orderings can be:

- All are single. {x
_{1}, x_{2}, ... , x_{n}} -
x
_{1}is single , others are paired contiguously(if**n**is odd). {x_{1}, (x_{2}, x_{3}), ...}

So on. So if we try to figure out a formula then to observe that.

For any x_{i}- x
_{i}can be kept single - x
_{i}can be paired with any other x_{j}provided i≠j

- x

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

**(number of ways xn can be paired * sub-problem excluding x**

*f*(n)=(n-1)**f*(n-2)_{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 10So 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions