HardNo. 1434
Number of Ways to Wear Different Hats to Each Other — LeetCode 1434 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Array, Dynamic Programming, Bitmask
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- hats = [[3,4],[4,5],[5]]
- Output
- 1
- Explanation
- There is only one way to choose hats given the conditions.
Python solution
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
g = defaultdict(list)
for i, h in enumerate(hats):
for v in h:
g[v].append(i)
mod = 10**9 + 7
n = len(hats)
m = max(max(h) for h in hats)
f = [[0] * (1 << n) for _ in range(m + 1)]
f[0][0] = 1
for i in range(1, m + 1):
for j in range(1 << n):
f[i][j] = f[i - 1][j]
for k in g[i]:
if j >> k & 1:
f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod
return f[m][-1]Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1434. Number of Ways to Wear Different Hats to Each Other is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0473 | Matchsticks to Square | Medium |
| 0526 | Beautiful Arrangement | Medium |
| 0638 | Shopping Offers | Medium |
| 0698 | Partition to K Equal Sum Subsets | Medium |
| 0805 | Split Array With Same Average | Hard |
| 0943 | Find the Shortest Superstring | Hard |
Frequently asked questions
- How hard is LeetCode 1434. Number of Ways to Wear Different Hats to Each Other?
LeetCode 1434. Number of Ways to Wear Different Hats to Each Other is rated Hard on LeetCode.
- What topics does LeetCode 1434. Number of Ways to Wear Different Hats to Each Other cover?
LeetCode 1434. Number of Ways to Wear Different Hats to Each Other is tagged Bit Manipulation, Array, Dynamic Programming and Bitmask on LeetCode.