Hat Combination

Hard
0/120
Average time to solve is 50m
profile
Contributed by
2 upvotes
Asked in companies
DirectiD.E.ShawCodenation

Problem statement

It is the birthday of the Ultimate Ninja Ankush, and his fellow Seito’s have decided to organize a party in the dojo. The Ultimate Ninja Ankush loves a party and brings hats for everyone, but the students are very choosy and prefer only some hats. Since Ankush is the Ultimate ninja, he loves a brain teaser. He wants to know the total Number of Combinations such that all students wear different hats.

There are ‘N’ students, and Ultimate Ninja Ankush has exactly 40 varieties of hats numbered from, each of the ‘N’ students have ‘M’ preference of hats out of the 40, and we want to know the total number of Combination such that all students wear different hats.

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

Given a list of integers hats, where ‘hats[i]’ is a list of all hats preferred by the i-th person. Return the number of ways that the ‘N’ students wear different hats to each other. Since the answer may be too large, return it modulo 10 ^ 9 + 7.

For example:

Given:
‘N’ = 2, ‘M’ = 3.
‘Hats’ = [[1, 2, 3],
          [3, 4, 5]]

The answer will be 8, the combinations can be (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5).
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N,’ where ‘N’ is the number of rows in ‘HATS’ and ‘M’ where ‘M’ is the number of columns in ‘HATS’.

The next ‘N’ line of each test case contains ‘M’ space-separated integers, which tell the preference of hats of the ‘i’ the student.
Output Format : 
For each test case, return the number of ways that the ‘N’ students wear different hats to each other. Since the answer may be too large, return it modulo 10 ^ 9 + 7.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10
1 <= ‘M’ <= 40
1 <= ‘HATS[i][j]’ <= 40

Time Limit: 1 sec.

Sample Input 1 :

2
2 3
1 2 3
3 4 5
3 3
1 2 3
1 2 4
1 2 5

Sample Output 1 :

8
13

Explanation of the Sample Input 1:

In the first test case, The answer will be 8. The combinations can be (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5).

In the second test case, The answer will be 13, the combinations can be (1,2,5),(1,4,5), (1,4,2), (2,1,5), (2,4,5),(2,4,1), (3,1,2), (3,1,5), (3,2,5), (3,2,1),(3,4,1), (3,4,2), (3,4,5).

Sample Input 2 :

2
4 4
1 2 3 4
1 2 3 4 
1 2 3 4
1 2 3 4
3 2
1 2
3 4
5 6
3 3

Sample Output 2 :

24
8
Hint

Can we use bitmasks to denote the state of each row?

Approaches (2)
Recursion Using bitmask.

In computing, numbers are internally represented in binary. This means, where we use an integer type for a variable, this will actually be represented internally as a summation of zeros and ones.

Bit masking allows us to use operations that work on bit-level.

  • Editing particular bits in a byte(s)
  • Checking if particular bit values are present or not.

You apply a mask to a value, wherein in our case, the value is our state 00000101, and a mask is again a binary number, which indicates the bits of interest.


 

The idea is, instead of thinking of a problem to assign hats to some students, think of assigning students to hats, that is, rehash the ‘HATS’ array such that we know what ‘HATS' have which student.


 

We represent the students as a bitmask, and all the bits are initially all the bits are off, representing that no students have been assigned any hats. At the end, if we set all the bits, we consider it as a valid combination, and our end goal is to count all valid combinations.


 

The steps are as follows:

  • We declare a 2-D vector ‘mp’, which has 41 rows representing the hats, and each row will contain some columns depending on how many students have the preference.
  • Loop through ‘HATS’ using ‘i’, ‘j’, and push ‘i + 1’ to ‘mp[‘HATS[i][j]’].
  • Maintain a ‘filledMask’ which denotes when all the students have been assigned hats, and we have found a valid combination.
  • To count the combinations, we use a helper function, ‘numberWaysHelper’, which takes ‘mp,’’hatId’,’curMask’, and ‘filledMask’ as input parameters, where ‘hatId’ represents the number of the hat for which we are processing, and ‘curMask’ which represents the students who have received a hat.
  • The base cases would be:
    • If ‘filledMask’ is equal to ‘curMask’, return 1, which means we found a valid combination.
    • If the ‘hatId’ is greater than 41, then return 0, which means an invalid combination, hence return 0.
  • Maintain a variable ‘totalWays’ = 0, which represents the total number of combinations.
  • One of the ways is to pass on for the current ‘hatId’. Therefore we recurse passing ‘hatId + 1’,’curMask’ as it is, and ‘filledMask’ as it is.
  • For other ways, we traverse, ‘mp[hatId]’ using ‘i’:
    • To check if we can assign the hat to the ‘i’th person, we check if (‘curMask’&(1 << ‘i-1’) == 0), we assign the ‘hatId’th hat to the ‘i’th person and recur for ‘hatId + 1’, ‘curMask’ | (1 << ‘i-1’), ‘filledMask’ as it is.
  • Finally return ‘totalWays’ % 1e9 + 7 as the final answer.
Time Complexity

O((2 ^ M) * (2 ^ N) * (N*M)), Where ‘N’ is the number of rows, and ‘M’ is the number of columns.

 

Since for each hat we can either assign it or not and each hat may be accessible to each student and we may decide to either assign hat to that student or not, therefore the overall time complexity will be O((2 ^ M) * (2 ^ N) * (N*M)).

Space Complexity

O((2 ^ M) * (2 ^ N)), Where ‘N’ is the number of rows, and ‘M’ is the number of columns.


Since we are using recursion and the call stack can reach a maximum height of (2 ^ M) * (2 ^ N).

Code Solution
(100% EXP penalty)
Hat Combination
Full screen
Console