Distinct Subsets Count

Moderate

0/80

Average time to solve is 40m

8 upvotes

Asked in companies

Problem statement

Given an array arr of N integers that may contain duplicate integers. The task is to return the count of subsets of the given array such that each subset contains only distinct elements.

Note:

As the answer can be large, return your answer modulo 10^9  + 7.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array (arr).

The second line contains 'N' single space-separated integers, representing the elements in the array.

Output format:

For each test case, print the count of subsets modulo 10^9+7 in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10 
1 <= N <= 10^5 
1 <= arr[i] <= 10^5 

Time limit: 1 second

Sample input 1:

1
4
1 2 2 5

Sample output 1:

Explanation For Sample Input 1 :

Subsets with distinct elements are: {1}, {2}, {2}, {5}, {1, 2}, {1, 2}, {2, 5}, {1,5}, {2,5}, {1, 2, 5}, {1, 2, 5}

For better understanding, let us take an array as {1, 2A, 2B, 5}  
Now, subsets can be {1}, {2A}, {2B}, {5}, {1, 2A}, {1,2B}, {2A, 5}, {1, 5}, {2B,5}, {1, 2A, 5}, {1, 2B, 5}

Sample input 2:

Sample output 2:

17
3

Hint 1

Hint 2

First off, observe that the question focuses on subsets of the array. A very simple technique to get this done is by creating all the possible subsets. Along with keeping all the subsets, we can maintain the count of all the subsets with no duplicates.

Approaches (2)

Approach 1

Approach 2

Brute Force

The idea is to call a helper function so as to create all possible subsets of the array.
- vector<int> current = the vector storing the current possible subset of the array.
- Recursive calls for generating all possible subsets.
We maintain a count variable to count the subsets which have no duplicate elements. Thus, in addition to the base case, we maintain a map so as to check if the frequency of any element exceeds 1.
We return the count of distinct subsets received from the helper function.

Time Complexity

O(2^N) per test case, where N is the number of elements.

In the worst case, we are generating all the subsets of an array. The possible number of subsets can be 2^N

Space Complexity

O(N), where N is the number of elements.

In the worst case, we are using extra map space and a recursive stack for every subset created.

(100% EXP penalty)

Distinct Subsets Count

Console