Number of Ways to Wear Different Hats to Each Other Solution
Number of Ways to Wear Different Hats to Each Other solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Ways to Wear Different Hats to Each Other is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Bit Manipulation, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n people and 40 kinds of hats labelled 1 to 40. hats[i] lists the hat labels that person i likes (the lists may have different lengths).
Count the ways to give every person one hat they like so that no two people wear the same hat. Two ways differ if some person wears a different hat.
Return the count modulo 10^9 + 7.
Example 1
Input: hats = [[1,2],[1,2]]
Output: 2
Example 2
Input: hats = [[1,2,3],[2,3],[1,4]]
Output: 6
Explanation: If person 2 takes hat 1, persons 0 and 1 share {2,3}: 2 ways. If person 2 takes hat 4, there are 3 × 2 choices minus the 2 clashes: 4 ways.
Example 3
Input: hats = [[7],[7]]
Output: 0
Constraints
n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i] contains distinct integers
Hints for Number of Ways to Wear Different Hats to Each Other
Hint 1
A bitmask over the 40 hats is far too big, but there are at most 10 people.
Hint 2
Flip the point of view: go through the hats one at a time and decide which person (if any) gets each hat.
Hint 3
Let
dp[mask]be the number of ways in which exactly the people inmaskhave hats, using the hats processed so far. Each new hat either stays unused or goes to one person who likes it and is not yet inmask.
How to solve Number of Ways to Wear Different Hats to Each Other
Iterate over hats instead of people: with at most 10 people, the set of people already wearing a hat fits in a 10-bit mask, and each hat moves the DP from a mask to a mask with one more person.
Approach
- Build
likes[h], the people who like hath. - Start with
dp[0] = 1. - For each hat
hfrom 1 to 40, walk the masks from largest to smallest; for each personpinlikes[h]not inmask, adddp[mask]todp[mask | 1<<p]modulo10^9 + 7. (Leavingdp[mask]as is means hathstays unused.) - Return
dp[2^n - 1].
Why it works
Every valid assignment gives each hat to at most one person, so it is described uniquely by the sequence of decisions "hat h goes to nobody / to person p" taken in hat order, and the DP counts exactly those sequences that end with everyone served. Walking the masks downward makes the update in place safe: a mask only feeds larger masks, which have already been visited for this hat, so no hat is handed out twice.
Complexity
- Time —
O(40 · 2^n · n) - Space —
O(2^n)
Pitfalls
- A DP over people with a mask of used hats needs 2^40 states — the hat-major order is the whole trick.
- Update masks in descending order (or into a fresh array) so a hat is not given to two people.
- Add modulo 10^9 + 7 at every step; the true count is enormous when many people like many hats.
Reference solution
Python
from typing import List
def numberWays(hats: List[List[int]]) -> int:
mod = 1000000007
n = len(hats)
full = 1 << n
likes = [[] for _ in range(41)]
for p in range(n):
for h in hats[p]:
likes[h].append(p)
dp = [0] * full
dp[0] = 1
for h in range(1, 41):
people = likes[h]
if not people:
continue
for mask in range(full - 1, -1, -1):
ways = dp[mask]
if not ways:
continue
for p in people:
bit = 1 << p
if not mask & bit:
dp[mask | bit] = (dp[mask | bit] + ways) % mod
return dp[full - 1]Java
public static int numberWays(int[][] hats) {
final int M = 1000000007;
int n = hats.length, full = 1 << n;
List<List<Integer>> likes = new ArrayList<>();
for (int h = 0; h <= 40; h++) likes.add(new ArrayList<Integer>());
for (int p = 0; p < n; p++) for (int h : hats[p]) likes.get(h).add(p);
int[] dp = new int[full];
dp[0] = 1;
for (int h = 1; h <= 40; h++) {
List<Integer> people = likes.get(h);
if (people.isEmpty()) continue;
for (int mask = full - 1; mask >= 0; mask--) {
if (dp[mask] == 0) continue;
for (int p : people) {
int bit = 1 << p;
if ((mask & bit) != 0) continue;
dp[mask | bit] = (dp[mask | bit] + dp[mask]) % M;
}
}
}
return dp[full - 1];
}C++
int numberWays(vector<vector<int>>& hats) {
const int M = 1000000007;
int n = hats.size(), full = 1 << n;
vector<vector<int>> likes(41);
for (int p = 0; p < n; p++) for (int h : hats[p]) likes[h].push_back(p);
vector<int> dp(full, 0);
dp[0] = 1;
for (int h = 1; h <= 40; h++) {
if (likes[h].empty()) continue;
for (int mask = full - 1; mask >= 0; mask--) {
if (!dp[mask]) continue;
for (int p : likes[h]) {
int bit = 1 << p;
if (mask & bit) continue;
dp[mask | bit] = (dp[mask | bit] + dp[mask]) % M;
}
}
}
return dp[full - 1];
}JavaScript
var numberWays = function(hats) {
var M = 1000000007, n = hats.length, full = 1 << n;
var likes = [];
for (var h = 0; h <= 40; h++) likes.push([]);
for (var p = 0; p < n; p++) {
for (var t = 0; t < hats[p].length; t++) likes[hats[p][t]].push(p);
}
var dp = new Array(full).fill(0);
dp[0] = 1;
for (var hat = 1; hat <= 40; hat++) {
var people = likes[hat];
if (!people.length) continue;
for (var mask = full - 1; mask >= 0; mask--) {
if (!dp[mask]) continue;
for (var q = 0; q < people.length; q++) {
var bit = 1 << people[q];
if (mask & bit) continue;
dp[mask | bit] = (dp[mask | bit] + dp[mask]) % M;
}
}
}
return dp[full - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming