Problem Statement
You are given n friends. Each friend has two choices:
Remain single.
Pair up with another friend.
A friend can be paired only once, and every possible arrangement must be counted.
Your task is to determine the total number of ways the n friends can either stay single or form valid pairs.
Examples
Example 1
Input
n = 3
Output
4
Explanation
The possible arrangements are:
{1}, {2}, {3}
{1}, {2,3}
{2}, {1,3}
{3}, {1,2}
Therefore, the answer is 4.
Example 2
Input
n = 2
Output
2
Possible arrangements:
{1}, {2}
{1,2}
Observing the Pattern
Let's compute the answer for the first few values.
| Number of Friends (n) | Ways |
|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 10 |
| 5 | 26 |
Looking at the table, we notice that each answer depends on the previous answers.
This suggests that Dynamic Programming (DP) can be used.
Key Idea
To derive the recurrence relation, focus only on the last friend (Friend n).
The last friend has only two possibilities.
Case 1: Friend n Remains Single
Suppose the last friend decides not to pair with anyone.
Example:
Friends:
1 2 3 4
Friend 4 stays single.
Now we only need to arrange:
1 2 3
The number of possible arrangements for these three friends is:
f(n-1)
Therefore, the contribution from this case is:
f(n-1)
Case 2: Friend n Forms a Pair
Now suppose Friend n wants to pair with someone.
If there are five friends:
1 2 3 4 5
Friend 5 can pair with:
1
2
3
4
There are:
(n-1)
possible partners.
After choosing one partner:
So only:
n-2
friends remain.
These remaining friends can arrange themselves in:
f(n-2)
ways.
Therefore, the total contribution from this case becomes:
(n-1) × f(n-2)
Recurrence Relation
Combining both cases:
f(n) = f(n-1) + (n-1) × f(n-2)
This recurrence completely solves the problem.
Base Cases
One Friend
f(1) = 1
Only one arrangement exists.
{1}
Two Friends
f(2) = 2
Possible arrangements:
{1}, {2}
{1,2}
Dry Run of the Formula
Suppose:
n = 4
We already know:
f(1) = 1
f(2) = 2
Calculate f(3)
f(3)
= f(2) + 2 × f(1)
= 2 + 2
= 4
Calculate f(4)
f(4)
= f(3) + 3 × f(2)
= 4 + 6
= 10
Final answer:
10
Dynamic Programming Approach
A recursive solution would repeatedly compute the same values.
Instead, we compute answers sequentially:
f(1)
↓
f(2)
↓
f(3)
↓
f(4)
↓
...
↓
f(n)
Notice something important.
Each value depends only on:
So we don't need an entire DP array.
We only keep:
prev2 = f(i-2)
prev1 = f(i-1)
This reduces the auxiliary space from O(n) to O(1).
Complete Java Solution
class Solution {
public int countFriendsPairings(int n) {
// Base cases
if (n == 1)
return 1;
if (n == 2)
return 2;
// f(1)
int prev2 = 1;
// f(2)
int prev1 = 2;
for (int i = 3; i <= n; i++) {
// f(i) = f(i-1) + (i-1) * f(i-2)
int curr = prev1 + (i - 1) * prev2;
// Move the window forward
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}
Code Explanation
Step 1: Handle Base Cases
if (n == 1)
return 1;
if (n == 2)
return 2;
The smallest inputs already have known answers, so we return them immediately without further computation.
Step 2: Store Previous Results
int prev2 = 1;
int prev1 = 2;
These variables store the last two computed answers.
prev2 = f(1)
prev1 = f(2)
Every future value depends only on these two previous values.
Step 3: Loop from 3 to n
for (int i = 3; i <= n; i++)
The loop computes the answer for each number of friends one by one.
i = 3
↓
i = 4
↓
i = 5
↓
...
↓
n
Step 4: Apply the Recurrence
int curr = prev1 + (i - 1) * prev2;
This line directly implements:
f(i) = f(i-1) + (i-1) × f(i-2)
Breaking it down:
The sum gives the total number of arrangements.
Step 5: Update Previous Values
prev2 = prev1;
prev1 = curr;
Once the current answer is calculated, we shift the variables for the next iteration.
Before updating:
prev2 = f(2)
prev1 = f(3)
After computing f(4):
prev2 = f(3)
prev1 = f(4)
The variables always represent the last two computed answers.
Step 6: Return the Final Answer
return prev1;
When the loop finishes, prev1 stores:
f(n)
which is the required answer.
Complete Dry Run
Suppose:
n = 5
Initial State
prev2 = 1
prev1 = 2
Iteration 1
i = 3
curr = 2 + (2 × 1)
= 4
Update:
prev2 = 2
prev1 = 4
Iteration 2
i = 4
curr = 4 + (3 × 2)
= 10
Update:
prev2 = 4
prev1 = 10
Iteration 3
i = 5
curr = 10 + (4 × 4)
= 26
Update:
prev2 = 10
prev1 = 26
Loop ends.
Return:
26
Visualization
f(1) = 1
↓
f(2) = 2
↓
f(3) = 2 + 2 × 1 = 4
↓
f(4) = 4 + 3 × 2 = 10
↓
f(5) = 10 + 4 × 4 = 26
Each answer is built from the previous two values.
Complexity Analysis
| Operation | Complexity |
|---|
| Time Complexity | O(n) |
| Auxiliary Space | O(1) |
The loop runs exactly once from 3 to n, and only three integer variables (prev2, prev1, and curr) are used.
Key Takeaways
Think about the last friend to derive the recurrence relation.
Every friend has only two choices:
The recurrence relation is:
f(n) = f(n-1) + (n-1) × f(n-2)
f(1) = 1
f(2) = 2
Summary
The Friends Pairing Problem is a classic Dynamic Programming problem that can be solved by considering the two possible choices for the last friend: remaining single or forming a pair. This leads to the recurrence relation f(n) = f(n-1) + (n-1) × f(n-2). By storing only the previous two computed values instead of an entire DP array, the solution achieves O(n) time complexity and O(1) auxiliary space, making it both efficient and scalable.