Number of Ways to Wear Different Hats to Each Other
Asked at Roblox
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Roblox | Hard | View all Roblox questions → |
How to Think About It
A mask over hats would be 2^40 states — far too many. A mask over people is only 2^10 = 1024.
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.
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.
Precompute, for each hat, the list of people who like it.
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).
What Trips People Up in Real Interviews
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.
Solution Code
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]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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.