/
FriendsPairingProblem.js
37 lines (35 loc) · 1.08 KB
/
FriendsPairingProblem.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* @author Anirudh Sharma
*
* Given N friends, each one 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 in which friends can remain single or can be paired up.
* Note: Since answer can be very large, return your answer mod 10^9+7.
*
* Constraints:
* 1 <= N <= 10^6
*/
const countFriendsPairings = (n) => {
// DP array for bottom up approach
const dp = Array(n + 1).fill(0);
// If there are zero persons, the number
// of ways will be zero
dp[0] = 0;
// If there is one person, it cannot be paired
dp[1] = 1;
// If there are two persons, then there can be only
// two ways - single and pair
dp[2] = 2;
// Loop for remaining persons
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
}
return dp[n] % 1000000007;
};
const main = () => {
console.log(countFriendsPairings(3));
console.log(countFriendsPairings(2));
console.log(countFriendsPairings(4));
console.log(countFriendsPairings(30));
};
main();