Approach
A naive solution is to try all possible combinations using backtracking. Assign the cap one by one for the first person, mark it visited and recursively call for the answer of the remaining sets.
Efficient Approach
An efficient approach is to solve using DP and bitmasking. The concept is to make use of the fact that there can be a maximum of 10 people. As a result, we can make an integer variable as a bitmask to track who is wearing a cap and who isn't.
Let index be the current cap number, i.e., caps from index 1 to (index-1) are already processed. Let mask represent the current state of people, i.e., if the ith bit is set, then the ith person has been already given a cap, else not.
Forming the recurrence relation for the function countWays(n, m, index, mask):
We have two options: the cap with the number(label) index will not be assigned to anyone or assigned to at least a person.
- Option 1: countWays(n, m, index+1, mask)
-
Option 2: Σ(countWays(n, m, index+1, mask | (1<<j)) for every jth person that has the cap with the label = index and has not been assigned any cap from the number 1 to (index-1).
In this option, the current cap is assigned to all those who have this cap and have not been assigned any cap before.
We can check if the jth person has not been designated any cap before using the mask and if we are assigning a cap to the jth person, set the jth bit.
By drawing the recursion tree for the above, we can see that some states will be repeated. So we will be using dynamic programming to store the answer for a particular state. It will be 2D dynamic programming: Dp[mask][index] where mask represents the current state of people and index represents the current cap number.
Code in C++
#include<iostream>
#include<vector>
using namespace std;
int MOD = 1e9 + 7;
long long countWays(
int n, int m,
int index,int mask,
vector<vector<long long> >& dp,
vector<int> v[]
){
if(mask==((1<<n) -1)){
// All the people have worn unique hats
return 1;
}
if(index>m){
// we don't have any hat to be alloted
return 0;
}
if(dp[mask][index]!=-1){
return dp[mask][index];
}
/*
we have 2 option
1st option - not allowing this ith cap to anyone
*/
dp[mask][index] = countWays(n,m,index+1,mask,dp,v);
/*
2nd option - allowing this ith cap to at least one person
*/
for(auto person:v[index]){
// first check if this person is not allocated any other hat
if(((1<<person)&mask)==0){
// allocate the ith cap to this person
int temp_mask = mask | (1<<person);
dp[mask][index] = (dp[mask][index] + countWays(n,m,index+1,temp_mask,dp,v))%MOD;
}
}
return dp[mask][index];
}
int numberWays(vector<vector<int>>& hats) {
int n = hats.size();
int hat_nos = 50;
vector<int> v[hat_nos+1];
for(int person=0;person<n;person++){
for(auto hat:hats[person]){
v[hat].push_back(person);
}
}
vector<vector<long long> > dp(1<<n, vector<long long>(hat_nos+1,-1));
return countWays(n,hat_nos,0,0,dp,v);
}
int main(){
vector<vector<int>> hats{
{1,2,3,4},
{1,2,3,4},
{1,2,3,4},
{1,2,3,4}
};
cout<<"Different ways to assign caps are: "<<numberWays(hats);
}
You can also try this code with Online C++ Compiler
Output
Different ways to assign caps are: 24
Time Complexity
Since we have n people and m(=50 in this case) different types of caps, the total number of DP states is m*2n. We will be looping over n people for each DP state; therefore, the time complexity for the above solution is O(n*m*2n).
Space Complexity
Since we are making a DP array to store the value for each DP state, the space complexity is O(m*2n) where m(=50 in this case) = total number of different types of caps and n = total number of people.
Read about Bitwise Operators in C here.
Check out Longest Common Substring
Frequently Asked Questions
1.What is the difference between bitwise AND operation and bitwise OR operation?
When both operands are true, the AND (&) operator returns true; otherwise, it returns false. The OR (|) operator returns true when either operand is true.
2.What is the C++ time complexity of a bitwise operation between 2 numbers?
The time complexity of a bitwise operation between 2 numbers is O(1).
3.What is the difference between signed int and an unsigned int?
The 32-bit signed integer data type could hold integer values in the range: [-231,231-1], whereas the 32-bit unsigned integer could have integer values in the range [0,232-1]. Since an unsigned integer can’t hold negative values, it doesn’t have the rightmost bit as a signed bit.
4.Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?
Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.
Key Takeaways
This article taught us how to count the number of ways to give each person a different cap when we have 50 different types of caps.
Since questions based on Bit manipulation and Dynamic Programming are frequently asked in coding rounds for various companies, we recommend you practice more problems based on Bit manipulation and Dynamic Programming on Coding Ninjas Studio.
Check out this problem - Minimum Coin Change Problem
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!
7+ registered 
