Last Updated: 1 Jul, 2021
Hat Combination
Hard
Asked in companies
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).
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.
Approaches
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.
Similar to the previous approach, It can be observed that there are recurring sub-problems. Therefore we can hash subproblems to speed up the recursion and better the time and space complexity.
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 ‘dp’ array to hash the subproblem, where ‘dp[i][j]’ represents, for the given ‘i’ hat and ‘j’th state of the mask, the total number of valid combinations.
- 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’, ‘dp’ 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.
- If we have already computed for the current state, we return ‘dp[hatId][curMask]’.
- 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.
- Assign ‘totalWays’ to ‘dp[hatId][curMask]’.
- Finally return ‘totalWays’ % 1e9 + 7 as the final answer.