# (12) DP: Friends Pairing Problem

[Question Link](https://practice.geeksforgeeks.org/problems/friends-pairing-problem5425/1#)

**Difficulty**: Easy

**Problem Statement**: Given N find a total number of ways in which it can pair up or remain single.

**Approach**: If `N = 1` then it can only remain in single. For `N = 2` it can remain single or pair up. For `N = 3` and above first it will remain single hence `dp[n - 1]` will be called on left `n-1` elements. Second it will combine with a element and now numbers remaining are `n-2` so `dp[n - 2]` will be called and that total `dp[n - 2]` will be `(n-1)` in number and hence `dp[n-2] * (n-1)`.

```
int countFriendsPairings(int n)
{
    int dp[n + 1], mod = 1e9 + 7;
    dp[0] = 0, dp[1] = 1, dp[2] = 2;
    for (int i = 3; i < n + 1; i++)
    {
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
        dp[i] = dp[i] % mod;
    }
    return dp[n];
}
``` 

**Subscribe to the newsletter so that you never miss any post or update just like this one.**

You can follow me on Hashnode for:

- Daily Data Structure and Algorithm based questions
- Getting knowledge of various development-related tools, concepts, and practices

 [Twitter](https://twitter.com/_Arsalaan_) ,  [GitHub](https://github.com/arsalanhub) ,  [LinkedIn](https://www.linkedin.com/in/mohammadarsalan/)  and  [Hashnode](https://hashnode.com/@mohdarsalan)