Friends Pairing Problem

Time: O(n)

Space: O(1)

Problem Overview

n friends can stay alone or pair up.

Intuition

n friends can stay alone or pair up. Fix friend n: either alone, leaving f(n-1) ways for the others, or pair with one of the other n-1 friends, leaving f(n-2) ways for each choice. That recurrence builds every valid matching of singles and disjoint pairs.

Algorithm

1Base: f(0) = f(1) = 1 (empty or one person alone).
2For i = 2..n: f(i) = f(i-1) + (i-1) * f(i-2).
3Keep only prev = f(i-2) and curr = f(i-1); update in place and return curr.

Example Walkthrough

Input: n = 3

1. f(2) = f(1) + 1*f(0) = 1 + 1 = 2 (both alone, or the pair).
2. f(3) = f(2) + 2*f(1) = 2 + 2 = 4.
3. The four matchings: all single; pair (1,2); pair (1,3); pair (2,3).

Output: 4

Common Pitfalls

• Multiply by (i-1), not by i - friend i cannot pair with themselves.
• Some GFG variants ask for answer modulo 1e9+7; this form assumes the raw count fits the return type.
• f(0)=1 is the empty pairing convention needed by the recurrence.
• O(n) DP is enough; no need to memoize a tree of recursive calls.

Friends Pairing Problem.java

Java

// Approach: Classic friends pairing recurrence. Friend n either stays single
// (then times f(n-1) ways for the rest) or pairs with any of the other n-1
// friends (times f(n-2) for each choice). So f(n) = f(n-1) + (n-1)*f(n-2) with
// f(0)=f(1)=1. Compute iteratively with two rolling variables.
// Time: O(n) Space: O(1)
class Solution {

    public int countFriendsPairings(int n) {
        int curr = 1, prev = 1;
        for (int i = 2; i <= n; i++) {
            int temp = curr + (prev * (i - 1));
            prev = curr;
            curr = temp;
        }

        return curr;
    }
}

Was this solution helpful?