×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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 x1, x2, ..., xn

Now, possible orderings can be:

  1. All are single. {x1, x2, ... , xn}
  2. x1 is single , others are paired contiguously(if n is odd). {x1, (x2, x3), ...}
    So on. So if we try to figure out a formula then to observe that.
    For any xi
    1. xi can be kept single
    2. xi can be paired with any other xj provided i≠j

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

Considering the above two facts about xi

If xn is kept single then f(n) = f(n-1) (same as number of ways excluding xn)
If xn is paired with any other friend then f(n)=(n-1)*f(n-2) (number of ways xn can be paired * sub-problem excluding xn 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:
    
Recursion tree

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


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.