========
Problem:
Given a list of N items. Each item can be assigned to multiple categories. How many ways can I take a pair of items that don't share a common category?
constraints:
- Number of items <= 100,000.
- Number of categories <= 30.
- Each item can be assigned to a maximum of 30 different categories.
Example:
We have 5 items
1st item is assigned to categories: 1, 3, and 5.
2nd item is assigned to categories: 2, and 6.
3rd item is assigned to categories: 2, 3, and 5.
4th item is assigned to category: 4.
5th item is assigned to categories: 1, and 2.
Answer is 5
(1,2),(1,4),(2,4),(3,4),(4,5).
Can anyone help me with how can I solve this problem?
Can you provide link to original statement?
Since the author has not replied yet, I am telling the source. This problem was asked to my friend also in an interview a few days ago. I also want to know its solution.
fwitt, Sorry for the delay in replying, and thanks for the help in advance.
I asked about this problem in an interview.
You can check this comment for explaining the problem
[DELETED]
" the number of pairs you can't choose is much smaller than the total possible number of pairs "
What if all items belong to only 1 category, there will be O(N^2) pairs
" With some numbers, in one category you can have at most 30 different elements those are (30 * 29) / 2 possible pairs which sums up to 435 possible different pairs "
What is some number? What are you considering as elements in a category? If you are considering it to be having a common group then this can be a lot bigger considering the above case.
You are totally right, I messed up the interpretation, I don't know how to solve the problem.
Please explain the statement clearly. What is given in the input? The number of items as well as the category of each item? Are pairs $$$(a,b)$$$ and $$$(b,a)$$$ different?
If so then iterate over all pairs of categories $$$(c1,c2)$$$ and then add $$$freq[c1] * freq[c2]$$$ to your answer.
You are misunderstanding the problem. Given a list of N items. Each item is assigned a list of categories(categories are represented by integer from 1 to M) . So you are given A: vector of vector which contains N items and A[i] is a vector which contains the categories which item i belongs to.
Find number of pairs of (i,j) such that i < j and the items don't have a common category (i.e no a,b exists such that A[i][a] = A[j][b])
Sorry for the delay in replying, and thanks for the help in advance.
I think adityagamer explained the problem nicely better than I did.
Are you sure about the constraint on number of categories? I saw a kinda similar problem but with constraint on number of categories <= 10.
For this constraint it can be solved in the following way:
Convert every element to its corresponding bit representation. For example if it has categories {1,3,5} then its bit representation is 10101. Now for every element i, we need to query number of elements such that they do not share any bit with ith element. Optimization 1: Take
mask = ~element[i]and then you need to find number of elements x in array such thatmask|x = mask. Optimization 2: There can be atmost 2^10 different queries, so it would be better to cache the result of queries(Or you can also just simply do offline queries). Finally just divide the answer by 2. Overall complexity = O(N * 2^M)