Do you think IIT Guwahati certified course can help you in your career?
Introduction-
Today, let’s learn about a famous and commonly asked Interview Problem, i.e., the number of ways to wear different hats to each other.
It is a famous and common problem that is solved using dp in its most optimized version.
Problem Statement:
There are N people and 40 types of hats (from 1 to 40). Given a list of integer hats, where hats[i] is the list of all hats preferred by i-th person, find the number of ways to wear different hats to each other for N people.
Examples:
If the given hats are: [[1, 2], [1, 4], [1]]
So, the only combination possible for all the 3 people to wear a hat is -
3rd person wearing Hat 1, 2nd person wearing Hat 4 and 1st person wearing Hat 2.
Hence, the possible ways here = 1.
Now, let's get started and learn various approaches to solve this problem.
Approach1 - Brute Force - Using Recursion
The naive (or brute force) solution to this problem could be finding all possible configurations of the number of ways to wear different hats to each other for N people.
So, we first find the maximum ways possible to assign hats = 2 ^ N - 1.
Then in recursion, we maintain two ways -
Current hat is not assigned to any hat
In a loop, try assigning hats to every person. If person P is assigned a hat, we skip that person or else we assign the hat to P-th person.
Note: The base case would be that if all the hats are assigned, return 0 (no more ways to assign hats) or if all people are assigned hats, return 1 (1 way i.e. directly assigning the hat to person).
Implementation-
Let’s have a look at its implementation in Java -
class Solution {
public int numberWays(List<List<Integer>> hats) {
int n = hats.size();
// List of people who can wear i-th hat
List<Integer>[] canWear = new List[41];
// Running Loop till 40 as 40 is the max type of hat
for (int i = 1; i <= 40; i++) canWear[i] = new ArrayList<>();
for (int i = 0; i < n; i++)
for (int hat : hats.get(i))
canWear[hat].add(i);
// (1 << n) - 1 as 2 ^ n - 1 maximum ways possible
return numWays(canWear, (1 << n) - 1, 1, 0);
}
/*
Number of Ways to assign 40 hats to n people
such that “assignedPeople” is the mask of list of people that were
assigned hat
*/
public int numWays(List<Integer>[] canWear, int allMask, int hat, int assignedPeople) {
// Check if different hats assigned to all people
if (assignedPeople == allMask) return 1;
// All hats assigned
if (hat > 40) return 0;
// People don't wear this hat
int ans = numWays(canWear, allMask, hat + 1, assignedPeople);
for (int p : canWear[hat]) {
// Skip if person “p” was assigned hat
if (((assignedPeople >> p) & 1) == 1) continue;
// Wear this hat for p-th person
ans += numWays(canWear, allMask, hat + 1, assignedPeople | (1 << p));
ans %= 1000000007;
}
return ans;
}
public static void main (String[] args){
Scanner s = new Scanner(System.in);
// Take Input
System.out.println("Enter number of people");
String n = s.next();
List<List<Integer> list = new ArrayList<>;
for (int i = 0; i < n ; i++){
List<Integer> hat = new ArrayList<>();
System.out.println("Enter number of hats and hats");
int hatn = s.nextInt();
for (int i = 0; i < hatn; i++){
hat.add(s.nextInt());
}
list.add(hat);
}
System.out.println("Number of ways to wear different hats to each other for N people "+ numberWays(list));
}
You can also try this code with Online C++ Compiler
Enter number of people 2
Enter number of hats and hats
3
3
5
1
Enter number of hats and hats
2
3
5
Number of ways to wear different hats to each other for N people 4
You can also try this code with Online C++ Compiler
Time Complexity: O(40 * 2 ^ N ^ N ), i.e., exponential as we generate and compare all the number of ways to wear different hats to each other for N people.
Space Complexity: O(1) as no extra space is being used.
Approach 2 - Using Dynamic Programming
We could optimize the time complexity of our previous approach by maintaining a dp array where dp[i][j] stores the current hat to be assigned at i - th index and assigned people at the jth index.
Recursive Tree:
Like this, there are many redundant calls.
Since the recursive approach had a lot of overlapping subproblems, the dp array would also help us avoid that repetitive work.
So, here we create a 2D dp array of dimensions 41 X 1024. 41 to store 40 hats indices and 1024 to store 1024 (as 1 << 10 = 1024 where 10 is the maximum number of people possible).
Using DP with Bit Masking and mask variable to check if all people are assigned a valid hat. If yes, directly 1 is returned or else the process is continued.
We try to assign 40 hats to N people and find a number of ways in doing so such that the assignedPeople is the mask of the list of people that are assigned a valid hat.
Approach 2a - Using Memoization
Implementation-
Let’s have a look at its implementation in Java -
class Solution {
public int numberWays(List<List<Integer>> hats) {
int n = hats.size();
// List of people who can wear i-th hat
List<Integer>[] canWear = new List[41];
// Running Loop till 40 as 40 is the max type of hat
for (int i = 1; i <= 40; i++) {
canWear[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++){
for (int hat : hats.get(i)){
canWear[hat].add(i);
}
}
// Forming dp array
Integer[][] dp = new Integer[41][1024];
// (1 << n) - 1 as 2^n - 1 maximum ways possible
return numWays(canWear, (1 << n) - 1, 1, 0, dp);
}
// Finding total possible ways to assign hats
public int numWays(List<Integer>[] canWear, int allMask, int hat, int assignedPeople, Integer[][] dp) {
// Check if different hats assigned to all people
if (assignedPeople == allMask) return 1;
// All hats assigned
if (hat > 40) return 0;
// Lookup in dp array
if (dp[hat][assignedPeople] != null) return dp[hat][assignedPeople];
// People don't wear this hat
int ans = numWays(canWear, allMask, hat + 1, assignedPeople, dp);
for (int p : canWear[hat]) {
// Skip if person `p` was assigned hat
if (((assignedPeople >> p) & 1) == 1) continue;
// Wear this hat for p_th person
ans += numWays(canWear, allMask, hat + 1, assignedPeople | (1 << p), dp);
ans %= 1000000007;
}
return dp[hat][assignedPeople] = ans;
}
public static void main (String[] args){
Scanner s = new Scanner(System.in);
// Take Input
System.out.println("Enter number of people");
String n = s.next();
List<List<Integer> list = new ArrayList<>;
for (int i = 0; i < n ; i++){
List<Integer> hat = new ArrayList<>();
System.out.println("Enter number of hats and hats");
int hatn = s.nextInt();
for (int i = 0; i < hatn; i++){
hat.add(s.nextInt());
}
list.add(hat);
}
System.out.println("Number of ways to wear different hats to each other for N people "+ numberWays(list));
}
}
You can also try this code with Online C++ Compiler
Enter number of people 2
Enter number of hats and hats
3
3
5
1
Enter number of hats and hats
2
3
5
Number of ways to wear different hats to each other for N people 4
You can also try this code with Online C++ Compiler
Time Complexity: O(40 * (2 ^ 10) * N) as there are total hats * assignedPeople = 40 * 2 ^ 10, where each state needs a loop upto ‘N’ times to calculate our answer.
Space Complexity: O((2 ^ 10) * 40) as extra space is used to store all the given hats to (2 ^ 10) possible people.
Where ‘N’ is the number of people.
Approach 2b - Using Bottom Up DP
Implementation-
Let’s have a look at its implementation in Java -
class Solution {
private static int MOD = 1000000007;
public int numberWays(List<List<Integer>> hats) {
int n = hats.size();
// Forming list of hats
List<Integer>[] h = new List[40];
// Forming an empty arraylist for all 40 type of hats
for (int i = 0; i < 40; i++) {
h[i] = new ArrayList<>();
}
for (int i = 0; i < hats.size(); i++) {
for (int hat : hats.get(i)) {
// Convert to 0-based indexing
h[hat - 1].add(i);
}
}
int[][] dp = new int[41][1 << n];
// Initializing
dp[0][0] = 1;
for (int i = 0; i < 40; i++) {
for (int j = 0; j < 1 << n; j++) {
dp[i+1][j] = dp[i][j];
for (int people: h[i]) {
int index = 1 << people;
if ((j & index) > 0) {
dp[i+1][j] = (dp[i+1][j] + dp[i][j^index]) % MOD;
}
}
}
}
return dp[40][(1 << n) - 1];
}
public static void main (String[] args){
Scanner s = new Scanner(System.in);
// Take Input
System.out.println("Enter number of people");
String n = s.next();
List<List<Integer> list = new ArrayList<>;
for (int i = 0; i < n ; i++){
List<Integer> hat = new ArrayList<>();
System.out.println("Enter number of hats and hats");
int hatn = s.nextInt();
for (int i = 0; i < hatn; i++){
hat.add(s.nextInt());
}
list.add(hat);
}
System.out.println("Number of ways to wear different hats to each other for N people "+ numberWays(list));
}
You can also try this code with Online C++ Compiler
Enter number of people 2
Enter number of hats and hats
3
3
5
1
Enter number of hats and hats
2
3
5
Number of ways to wear different hats to each other for N people 4
You can also try this code with Online C++ Compiler
Time Complexity: O(40 * (2 ^ 10) * N) as there are total hats*assignedPeople = 40 * 2 ^ 10, where each state needs a loop upto ‘N’ times to calculate our answer.
Space Complexity: O((2 ^ N) * 40) as extra space is used to store all the given hats to (2 ^ N) possible people.
Where ‘N’ is the number of people.
Frequently Asked Questions-
What is dynamic programming?
Ans. Dynamic programming is both a mathematical optimization method and a computer programming method mainly used to optimize plain recursion.
2. What are two ways to apply dynamic programming?
Ans. The two ways to apply dp are bottom-up (i.e., iterative way) and top-down (i.e., using dp in recursion, commonly known as memoization).
3. What is a subsequence?
Ans. A subsequence of a string is a new string generated from the original string with some (or none) characters deleted without changing the relative order of the remaining characters.
4. Why are we optimising using dp?
Ans: This is because the recursive approach had a lot of overlapping subproblems, the dp array would also help us avoid that repetitive work.
In this blog, we learned various approaches to the number of ways to wear different hats to each other for N people.
The number of ways to wear different hats to each other for N people is a standard recursive problem that is optimized via dp.
The optimized time complexity of this problem is O(N ^ 2) as for each character at an index, we are ca;culating and comparing the LCS value till the ith and jth index value of string1 and string2 respectively.
Check out more blogs on different dp problems like LCS, Friends Pairing Problem to read more about these topics in detail. And if you liked this blog, share it with your friends!
Practice a variety of on Coding Ninjas Studio platform where you can find questions asked in all big-tech giants.
24+ registered 
