Number of Ways to Wear Different Hats to Each Other

Hard
1342.

Number of Ways to Wear Different Hats to Each Other

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.

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.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] contains distinct integers
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} hats
 * @return {number}
 */
var numberWays = function(hats) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] contains distinct integers

Hints for Number of Ways to Wear Different Hats to Each Other

  1. Hint 1

    A bitmask over the 40 hats is far too big, but there are at most 10 people.

  2. Hint 2

    Flip the point of view: go through the hats one at a time and decide which person (if any) gets each hat.

  3. Hint 3

    Let dp[mask] be the number of ways in which exactly the people in mask have 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 in mask.

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

  1. Build likes[h], the people who like hat h.
  2. Start with dp[0] = 1.
  3. For each hat h from 1 to 40, walk the masks from largest to smallest; for each person p in likes[h] not in mask, add dp[mask] to dp[mask | 1<<p] modulo 10^9 + 7. (Leaving dp[mask] as is means hat h stays unused.)
  4. 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