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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Wear Different Hats to Each Other

Number: 1531

Difficulty: Hard

Paid? No

Companies: Mindtickle

Problem Description

Given n people and 40 types of hats (labeled 1 through 40), each person has a list of hats they prefer. The task is to count the number of ways to assign different hats to each person such that every person wears a hat they like. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • Instead of assigning hats to people, consider iterating over hats and assigning them to possible people.
  • Use a bitmask to represent which people have already been assigned a hat (since n ≤ 10, the maximum bitmask size is 2^10 = 1024).
  • Build a mapping from each hat to the list of people who like that hat.
  • Use dynamic programming (DP) where the state is a bitmask representing who has been assigned hats so far.
  • For each hat, update the DP table by trying to assign it to each person (in the current state) who prefers that hat and who has not been assigned a hat already.

Space and Time Complexity

Time Complexity: O(40 * 2^n * n) in the worst-case scenario. Space Complexity: O(2^n) for the DP table.

Solution

The solution uses dynamic programming with bit masking. First, we precompute a list for each hat (from 1 to 40) containing the indices of people who like that hat. Then, we use a DP array where dp[mask] indicates the number of ways to assign hats such that the people corresponding to the bits in mask have been given hats. We iterate over each hat and try to assign it in all possible ways to people that like that hat and who have not been assigned a hat in the current mask. The final answer is dp[(1 << n) - 1], meaning all people have been assigned hats. This approach efficiently manages states since n is small.

Code Solutions

MOD = 10**9 + 7

def numberWays(hats):
    n = len(hats)
    # Mapping from hatID to list of persons who like this hat.
    hat_to_people = {hat: [] for hat in range(1, 41)}
    for person, preferred_hats in enumerate(hats):
        for hat in preferred_hats:
            hat_to_people[hat].append(person)
    
    # dp[mask] where mask is a bitmask of persons who have been assigned hats.
    dp = [0] * (1 << n)
    dp[0] = 1  # No one has a hat, one way.
    
    # Iterate over each hat.
    for hat in range(1, 41):
        # We'll update the dp table in reverse order to avoid overcounting.
        new_dp = dp[:]  # Copy current state
        for mask in range(1 << n):
            # Try to assign current hat to one of the persons who like it and hasn't got a hat in `mask`
            for person in hat_to_people[hat]:
                if mask & (1 << person) == 0:
                    new_mask = mask | (1 << person)
                    new_dp[new_mask] = (new_dp[new_mask] + dp[mask]) % MOD
        dp = new_dp
    return dp[(1 << n) - 1]

# Example usage:
print(numberWays([[3,4],[4,5],[5]]))  # Output: 1
← Back to All Questions