Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Efficient Approach
4.
Code in C++
4.1.
Output
4.2.
Time Complexity 
4.3.
Space Complexity 
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Count the number of ways you can give each person a different cap

Author Gaurish Anand
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Bitwise Algorithms are used to perform operations on bits. Bitwise operations are much faster and are sometimes even used to improve the efficiency of a program.

It’ll be necessary to think about data at the bit level on occasion, and we'll have to work with each data bit separately. To make our activity more manageable, we may need to use binary operators to turn on/off particular data bits. Six major binary operators that make it easy to conduct operations and change data bits are: 

  1. & (Bitwise AND)
  2. | (Bitwise OR)
  3. ^ (Bitwise XOR)
  4. << (Left shift)
  5. >> (Right shift)
  6. ~ (Bitwise NOT)


You can go through this article to learn more about the above binary operators. In this blog, we will be discussing a problem where we will solve the problem using bit masking and dynamic programming. 

Bitmasking: Assume we have a set of numbers ranging from 1 to N. We can represent a subset of this set using N bits(also known as masks). If the ith element is selected in the subset, that bit will be set; otherwise, that bit will be unset. For example, the mask 001101 denotes that 1st,3rd, and 4th items are selected in this subset. 

Since we know we can have 2n subsets for a set of N numbers; thus there are 2masks to represent these subsets ranging in [0,2n) where each integer, when expressed in binary form, represents a mask.

Problem Statement

There are n people and m different caps labeled from 1 to m. Each person has a list of the caps available to them.
Count the number of ways to assign caps to n people where you have to give each person a different cap. Since, the number of ways can be large, return the answer modulo 109 + 7.

Constraints: 

  • << 10
  • << 50 
     

Input Format: You are given a 2D array hat[][] where hat[i] represents the list of caps available to the ith person where 1<=hat[i][[j]<=50 for every 1<=j<=n , where n=total number of persons. Example: 

Input: availableCaps =  [[3,5,1], [3,5]]
Output: 4
Explanation: {3,5}, {5,3}, {1,3} and {1,5} are the 4 ways to assign the caps.

Input: availableCaps = [[3,4], [4,5], [5]]
Output: 1
Explanation:{3,4,5} is the only way to assign the caps.

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

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. 

  1. Option 1: countWays(n, m, index+1, mask)
  2. 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);
} 

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!

Previous article
Number of Ways to Wear Different Hats to Each Other
Next article
Count numbers from a given range whose product of digits is K
Live masterclass