HardArrayDynamic ProgrammingBit ManipulationBitmaskUpdated Sep 2026

1434. Number of Ways to Wear Different Hats to Each Other

Asked at Roblox

Difficulty

Hard

Time

O(40 * 2^n * n)

Space

O(2^n)

Pattern

Array

Companies

1

Problem

There are n people and 40 types of hats, numbered 1 to 40. You are given a 2D array hats, where hats[i] lists the hat numbers that person i is willing to wear.

Count the number of ways to give every person exactly one hat so that no two people wear the same hat and each person gets a hat from their own list. Two ways are different if at least one person ends up with a different hat.

Because the count can be huge, return it modulo 10^9 + 7. If nobody can be satisfied, the answer is 0.

Who can wear which hat

hatsp0p1p234455Person 0 likes hats 3 and 4, person 1 likes 4 and 5,person 2 only likes 5.hats used345012The only valid assignment is p0→3, p1→4, p2→5, so theanswer is 1.
Each person picks one hat from their own list, and no hat may be used twice.

Constraints

  • ●n == hats.length
  • ●1 <= n <= 10
  • ●1 <= hats[i].length <= 40
  • ●1 <= hats[i][j] <= 40
  • ●hats[i] contains only unique integers

Examples

Example 1
Inputhats = [[3,4],[4,5],[5]]
Output1
WhyPerson 2 only accepts hat 5, so hat 5 is taken. Person 1 then must take hat 4 (hat 5 is gone), and person 0 is left with hat 3. Only one assignment works.
Example 2
Inputhats = [[3,5,1],[3,5]]
Output4
WhyThe two people must get two different hats from {1,3,5}. The valid ordered pairs are (3,5), (5,3), (1,3) and (1,5) — four ways in total.
Example 3
Inputhats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output24
WhyEveryone accepts all four hats, so we just count the ways to give four distinct hats to four people: 4! = 24.

Asked At

1 companies
CompanyDifficulty
RobloxHardView all Roblox questions →

How to Think About It

1

A mask over hats would be 2^40 states — far too many. A mask over people is only 2^10 = 1024.

2

Key insight: process hats one at a time. dp[mask] = number of ways to assign hats (among those processed so far) to exactly the people in mask.

3

For each hat, either nobody new wears it (dp unchanged), or it goes to one person who likes it and is not yet in mask. Iterate masks from high to low so each hat is used at most once, like a 0/1 knapsack.

4

Precompute, for each hat, the list of people who like it.

5

The answer is dp[(1 << n) - 1] after all 40 hats.

Optimal Approach

Step 1: likers[h] = people who like hat h.
Step 2: dp = [0] * (1 << n), dp[0] = 1.
Step 3: For each hat h from 1 to 40:
For mask from full down to 0:
For each person p in likers[h] not in mask:
dp[mask | (1 << p)] += dp[mask] (mod).
Step 4: Return dp[full].

Time: O(40 * 2^n * n). Space: O(2^n).

Bitmask dp over people, one hat at a time

dp after hat 30000010100111100Hat 3 can only go to person 0, so mask 001 becomesreachable from mask 000.dp after hat 40000010100111111Hat 4 can go to person 0 or person 1, filling masks010 and 011.dp after hat 500000101001110010111011111110001Hat 5 can only go to person 2, so only mask 011 canreach the full mask 111 — one way.dp[mask | (1<<p)] += dp[mask]for p in likers[h] not in maskanswer = dp[(1<<n) - 1]
dp[mask] counts ways to cover exactly the people in mask using hats seen so far; each new hat may go to one uncovered person who likes it.
ComplexityTime O(40 * 2^n * n)Space O(2^n)We loop over 40 hats, and for each hat we scan all 2^n masks and try each of the n people, so the cost is 40 * 2^n * n; the dp array of size 2^n dominates memory.

What Trips People Up in Real Interviews

1

Bitmasking over hats instead of people. Always put the smaller dimension in the mask.

2

Iterating masks upward, which lets one hat be assigned to two people in the same round.

3

Backtracking over people with no memoization — exponential in the number of hats.

4

Forgetting the modulo.

Solution Code

O(40 * 2^n * n) time
def numberWays(hats):
    MOD = 10**9 + 7
    n = len(hats)
    likers = [[] for _ in range(41)]
    for p, hs in enumerate(hats):
        for h in hs:
            likers[h].append(p)
    full = (1 << n) - 1
    dp = [0] * (1 << n)
    dp[0] = 1
    for h in range(1, 41):
        if not likers[h]:
            continue
        for mask in range(full, -1, -1):
            if dp[mask] == 0:
                continue
            for p in likers[h]:
                if not mask & (1 << p):
                    nm = mask | (1 << p)
                    dp[nm] = (dp[nm] + dp[mask]) % MOD
    return dp[full]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Ways to Wear Different Hats to Each Other problem?

Number of Ways to Wear Different Hats to Each Other gives each of up to 10 people a list of hats they like (40 hat types), and asks how many ways everyone can wear a different hat they like, modulo `10^9 + 7`. The trick is choosing the right dimension for the bitmask: mask over the 10 people, iterate over the 40 hats.

How do you solve Number of Ways to Wear Different Hats to Each Other?

The optimal approach runs in O(40 * 2^n * n) time and O(2^n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Ways to Wear Different Hats to Each Other?

Number of Ways to Wear Different Hats to Each Other is asked at Roblox. It is a hard difficulty problem.

What are common mistakes on Number of Ways to Wear Different Hats to Each Other?
  • Bitmasking over hats instead of people. Always put the smaller dimension in the mask.
  • Iterating masks upward, which lets one hat be assigned to two people in the same round.
  • Backtracking over people with no memoization — exponential in the number of hats.
  • Forgetting the modulo.