{x}
blog image

Number of Ways to Wear Different Hats to Each Other

There are n people and 40 types of hats labeled from 1 to 40.

Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the ith person.

Return the number of ways that the n people wear different hats to each other.

Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats:
(3,5), (5,3), (1,3) and (1,5)

Example 3:

Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

 

Constraints:

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] contains a list of unique integers.

Solution Explanation: Number of Ways to Wear Different Hats

This problem asks to find the number of ways to assign 40 different hats to n people, where each person has a preference list of hats they like. The constraints are that each person must wear exactly one hat, and no two people can wear the same hat. The solution leverages dynamic programming with bit manipulation for efficient state representation.

Approach: Dynamic Programming with Bitmasks

  1. Data Structures:

    • g: A dictionary (or array) mapping hat ID to the list of people who like that hat. This preprocesses the input hats for faster lookup.
    • f: A 2D array (or dictionary) representing the DP table. f[i][j] stores the number of ways to assign hats up to hat i such that the bitmask j represents the set of people who have already been assigned a hat. A bit set to '1' indicates the corresponding person has a hat, and '0' means they don't.

  2. Base Case:

    • f[0][0] = 1: There's one way to assign no hats to no people.

  3. State Transition: For each hat i and bitmask j, we have two possibilities:

    • Don't assign hat i: The number of ways remains the same as the previous hat, f[i-1][j].
    • Assign hat i: We iterate through each person k who likes hat i. If person k hasn't already been assigned a hat (bit k in j is 0), we can assign hat i to them. The new bitmask becomes j ^ (1 << k) (XORing with 1 << k flips the k-th bit). The number of ways in this case is f[i-1][j ^ (1 << k)]. We add this to the count from not assigning the hat.

  4. Final Answer:

    • f[m][(1 << n) - 1]: The final answer is the value in the DP table corresponding to the last hat (m) and the bitmask where all bits are set (all people have hats).

Time and Space Complexity Analysis:

  • Time Complexity: O(m * 2n * n), where m is the maximum hat ID (40 in this problem) and n is the number of people (maximum 10). The outer loop iterates through hats, the second loop iterates through all possible bitmasks (2n), and the inner loop iterates through people who like the current hat (at most n).

  • Space Complexity: O(m * 2n) to store the DP table f.

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples provided in the original response accurately reflect the algorithm described above. They demonstrate the implementation in various programming languages, showing the DP table construction and calculation of the final answer modulo 109 + 7. The use of bit manipulation makes the code concise and efficient. Note that the Python code uses defaultdict for efficient handling of the g dictionary, while the other languages use arrays or lists.