Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-
2.
Approach1 - Brute Force - Using Recursion
3.
Time and Space Complexity-
4.
Approach 2 - Using Dynamic Programming
5.
Approach 2a - Using Memoization
6.
Time and Space Complexity-
7.
Approach 2b - Using Bottom Up DP
8.
 
9.
Time and Space Complexity-
10.
Frequently Asked Questions-
11.
Key Takeaways-
Last Updated: Mar 27, 2024

Number of Ways to Wear Different Hats to Each Other

Author Raksha Jain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

 

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 - 

  1. Current hat is not assigned to any hat
  2. 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));
}

 

Output:

 

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

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Time and Space Complexity-

 

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));
}
}

 

 

Output:

 

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

 

Time and Space Complexity-

 

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));
}

 

Output:

 

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

 

Time and Space Complexity-

 

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-

 

  1. 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.

 

Key Takeaways-

  

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 this problem - Count Ways To Reach The Nth Stair 

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.

 

Previous article
Minimum Number Of Days To Debug All Programs
Next article
Count the number of ways you can give each person a different cap
Live masterclass