Watch 10 video solutions for Number of Ways to Wear Different Hats to Each Other, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Ashish Pratap Singh has 1,002,177 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i] contains a list of unique integers.