We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Wear Different Hats to Each Other

Difficulty: Hard

Problem Description

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 n people can wear different hats from each other. Since the answer may be too large, return it modulo 10^9 + 7.

Key Insights

  • Each person can only wear a hat from their preferred list.
  • No two people can wear the same hat.
  • The problem can be approached using dynamic programming and bit manipulation to track which hats have been taken.
  • The constraints allow for bitmasking since the number of people is limited to 10 and there are 40 types of hats.

Space and Time Complexity

Time Complexity: O(2^n * n * m), where n is the number of people and m is the average number of hats per person.
Space Complexity: O(2^n), for storing the dynamic programming state.

Solution

The solution utilizes dynamic programming combined with bit masking to represent the state of which hats have been taken. We will maintain a DP array where each index represents a state of hats assigned to people. The algorithm iterates through each person and their preferred hats, updating the DP array to count the number of ways to assign hats while ensuring no two people wear the same hat.

Code Solutions

def numberOfWays(hats):
    MOD = 10**9 + 7
    n = len(hats)
    dp = [0] * (1 << n)
    dp[0] = 1
    
    # Map each hat to the list of people who can wear it
    hat_to_people = [[] for _ in range(41)]
    for person in range(n):
        for hat in hats[person]:
            hat_to_people[hat].append(person)
    
    # Iterate over all hats
    for hat in range(1, 41):
        for mask in range((1 << n) - 1, -1, -1):
            for person in hat_to_people[hat]:
                if mask & (1 << person) == 0:  # If the person has not worn a hat
                    dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD
    
    return dp[(1 << n) - 1]
← Back to All Questions