========
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?