Count Good Subsets

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
Snapdeal Ltd.RED HEALTHCapegemini Consulting India Private Limited

Problem statement

You are given an array ‘ARR’ of size ‘N’ consisting of distinct elements. Your task is to find the total number of good subsets. A subset is called a good subset when you can rearrange the elements of the subset in such a way that each element divides the next element in order. Two subsets are different from each other if there is an element in one subset, which does not exist in the other.

For example :

Consider ARR = [2, 4, 5, 15], all possible good subsets following the given conditions are (2), (4), (5), (15), (2,4), and (5,15). Hence, the total number of good subsets is 6 in this case.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains a single integer, 'N', denoting the number of elements in the array.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.

Output Format :

For each test case, print a single integer - the total number of good subsets.

Print the output of each test case in a separate line.

Constraints :

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

All elements present in the array ARR are unique.

Time limit: 1 sec

Sample Input 1 :

2
2 
2 4
3
2 3 6

Sample Output 1 :

3
5

Explanation Of Sample Input 1 :

For the first test case, 
All possible good subsets following the given conditions are (2), (4), and (2,4). Hence, the total number of good subsets is 3 in this case.

For the second test case,
All possible good subsets following the given conditions are (2), (3), (6), (2,6), and (3,6). Hence, the total number of good subsets is 5 in this case.

Sample Input 2 :

2
3
4 2 8
4
2 3 5 7

Sample Output 2 :

7
4
Hint

Try to think of a recursive approach to find the total number of good subsets.

Approaches (3)
Recursion

The idea is to use a recursive approach to find all subsets of the array. The recursive idea is very clear that there are only two choices for any element in the array, either to include the element in the subset or do not include the element. Using this idea, we can find all subsets recursively, and we will check if the subset follows the given conditions.

We will define a function allSubsets(ARR, subset, index) to find all subsets of ARR. We will create an array subset to store the numbers present in the subset. Our final answer will be the total number of good subsets following the given conditions.

 

Working of the Recursive function: 

  1. If index is equal to N, then we will check if the elements present in the array subsets follow the given conditions, then we will return 1. Otherwise, we will return 0. This will serve as the base case for our recursive function.
  2. There are two cases for each element in the array ARR. The first case is when the element ARR[index] is not included in the subset. We will find firstAnswer, which is equal to allSubsets(ARR, subset, index+1).
  3. The second case when the element ARR[index] is included in the subset. So, we will insert ARR[index] in the array subset, and we will find secondAnswer, which is equal to allSubsets(ARR, subset, index+1).
  4. In the end, we will return firstAnswer + secondAnswer.
Time Complexity

O(2^N), where N denotes the number of elements in the array.

 

In each recursive call to the allSubsets we are making 2 recursive calls. Therefore, for N elements, we will be calling the allSubsets 2^N times. Hence, the overall Time Complexity is O(2^N).

Space Complexity

O(N), where N denotes the number of elements in the array.

 

The maximum number of elements in the array subset is N when all elements from ARR are present in the array subset. Hence, the overall Space Complexity is O(N)).

Code Solution
(100% EXP penalty)
Count Good Subsets
Full screen
Console