Count Good Subsets
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.

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

Question

Count Good Subsets

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.

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

Accepted Answer

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:

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.
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).
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).
In the end, we will return firstAnswer + secondAnswer.

Space Complexity: O(n)Explanation:

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)).

Time Complexity: O(2^n)Explanation:

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).

Accepted Answer

Dynamic Programming

A simple method is to sort the given array and traverse through the array to find the total number of good subsets with each array element as the rear element of the subset.

Our approach will be to construct an array distinctSubsets to store the total number of subsets following the given condition with ARR[i] as the rear element of the subset. We will sort the array ARR. We will iterate index from 0 to N-1, and in each iteration, we will iterate pos from 0 to index-1.

Now, there will be two cases,

If ARR[pos] divides ARR[index], then we can insert ARR[index] in those subsets in which the rear element is ARR[pos]. So, we will increment distinctSubsets[index] by distinctSubsets[pos].
If ARR[pos] does not divide ARR[index], then we cannot insert ARR[index] in those subsets in which the rear element is ARR[pos].

The subset elements can only be arranged in increasing order such that each element divides the next element in order. Due to this, we are sorting the array and traversing through the array to find the total number of subsets in which we can append the array element.

Algorithm:

We will set totalSubsets as 0. The variable totalSubsets stores the total number of good subsets.
Create an array distinctSubsets of size N with the value 1 at each position, which stores the total number of good subsets that can be created with each element of the array ARR as the rear element of the subset.
Sort the array ARR.
Iterate index from 0 to N-1,
- Iterate pos from 0 to index-1,
  - We will check if ARR[index] can be divided by ARR[pos],
    - We will increment distinctSubsets[index] by distinctSubsets[pos].
- Increment totalSubsets by distinctSubsets[index].
Return the variable totalSubsets.

Space Complexity: O(n)Explanation:

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

The Space Complexity O(N) is used to store the total number of good subsets with each array element as the rear element of the subset. Hence, the overall Space Complexity is O(N).

Time Complexity: O(n^2)Explanation:

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

We are doing N iterations, and in each iteration, it takes O(N) time to traverse through the array ARR to find the total number of distinct good subsets. Hence, the overall Time Complexity is O(N^2).

Java (SE 1.8)

/*

   Time Complexity: O(N^2)

   Space Complexity: O(N)



   Where N is the number of elements in the array.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution 

{

    public static int countGoodSubsets(ArrayList arr) 

    {

        int n = arr.size();



        // The variable totalSubsets stores the total number of good subsets

        int totalSubsets = 0;

    

        // Create an array distinctSubsets of size N with the value 1 at each position

        ArrayList distinctSubsets = new ArrayList<>(n);

        for(int i=0 ; i        {

            distinctSubsets.add(1);

        }

    

        // Sort the array

        Collections.sort(arr);

        

        // Traverse through the array ARR

        for (int index = 0; index < n; index++) 

        {

            for (int pos = 0; pos < index; pos++) 

            {

                // Check if ARR[index] can be divided by ARR[pos]

                if (arr.get(index) % arr.get(pos) == 0) 

                {

                    distinctSubsets.set(index , distinctSubsets.get(index) + distinctSubsets.get(pos));

                }

            }

    

            // Increment totalSubsets by distinctSubsets[index]

            totalSubsets += distinctSubsets.get(index);

        }

    

        // Return the variable totalSubsets

        return totalSubsets;

	}



}

Python (3.5)

'''

   Time Complexity: O(N^2)

   Space Complexity: O(N)



   Where N is the number of elements in the array.

'''



def countGoodSubsets(arr):



    n = len(arr)



    # The variable totalSubsets stores the total number of good subsets

    totalSubsets = 0



    # Create an array distinctSubsets of size N with the value 1 at each position

    distinctSubsets = [1 for j in range(n)]



    # Sort the array

    arr.sort()



    # Traverse through the array ARR

    for index in range(n):



        for pos in range(index):

            

            # Check if ARR[index] can be divided by ARR[pos]

            if (arr[index] % arr[pos] == 0):



                distinctSubsets[index] += distinctSubsets[pos]



        # Increment totalSubsets by distinctSubsets[index]

        totalSubsets += distinctSubsets[index]



    # Return the variable totalSubsets

    return totalSubsets

C++ (g++ 5.4)

/*

   Time Complexity: O(N^2)

   Space Complexity: O(N)



   Where N is the number of elements in the array.

*/



#include



int countGoodSubsets(vector &arr) 

{

    int n = arr.size();



    // The variable totalSubsets stores the total number of good subsets

    int totalSubsets = 0;



    // Create an array distinctSubsets of size N with the value 1 at each position

    vector distinctSubsets(n, 1);



    // Sort the array

    sort(arr.begin(), arr.end());

    

    // Traverse through the array ARR

    for (int index = 0; index < n; index++) 

    {

        for (int pos = 0; pos < index; pos++) 

        {

            // Check if ARR[index] can be divided by ARR[pos]

            if (arr[index] % arr[pos] == 0) 

            {

                distinctSubsets[index] += distinctSubsets[pos];

            }

        }



        // Increment totalSubsets by distinctSubsets[index]

        totalSubsets += distinctSubsets[index];

    }



    // Return the variable totalSubsets

    return totalSubsets;

}

Accepted Answer

Sieve based approach

In the previous approach, we are traversing through the array to find the total number of subsets in which we can append the array element, but in this approach, we will be traversing through all the possible elements that we can append in the subset, i.e., its multiples. We are trying to create a subset such that each element divides the next element of the subset. So, our approach will be to traverse through all possible elements such that the rear element of the subset divides that particular element.

We will construct an array distinctSubsets of size Max(ARR), and we will sort the array ARR. We will iterate index from 0 to N-1, and in each iteration, we will iterate pos from 2*ARR[index] to Max(ARR) and set element as ARR[index].

We are traversing through all possible values such that the value pos can be divided by element. So, we can insert pos in those sets whose rear element is element. We will increment distinctSubsets[pos] by distinctSubsets[element].
Increment pos by element.

Algorithm:

We will set totalSubsets as 0 and maxElement as the maximum element in the array ARR. The variable totalSubsets stores the total number of good subsets.
Create an array distinctSubsets of size maxElement+1 with value 1 at each position.
Sort the array ARR.
Iterate index from 0 to N-1,
- We will set element as ARR[index] and set pos as 2*element.
- Iterate till pos is less than or equal to maxElement,
  - Increment distinctSubsets[pos] by distinctSubsets[element].
  - Increment pos by element.
- Increment totalSubsets by distinctSubsets[element].
Return the variable totalSubsets.

Space Complexity: OtherExplanation:

O(Max(ARR)), where ARR denotes the given array of size N.

We are creating an array with the Space Complexity O(Max(ARR)) to apply the sieve-based approach to the values present in the array ARR. Hence, the overall Space Complexity is O(Max(ARR)).

Time Complexity: O(logn)Explanation:

O(N*Log(N) + Max(ARR)*Log(Max(ARR))), where N denotes the number of elements in the array.

The Time Complexity to sort all elements present in the array is O(N*Log(N)). The Time Complexity to find the total number of good subsets using sieve based approach is O(Max(ARR)*Log(Max(ARR))). Hence the overall Time Complexity is O(N*Log(N) + Max(ARR)*Log(Max(ARR))).

Java (SE 1.8)

/*

   Time Complexity: O(N*Log(N) + Max(ARR)*Log(Max(ARR)))

   Space Complexity: O(Max(ARR))



   Where N is the number of elements in the array.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution 

{

    public static int countGoodSubsets(ArrayList arr) 

    {

        int n = arr.size();



        // The variable totalSubsets stores the total number of good subsets

        int totalSubsets = 0;

    

        // The variable maxElement stores the maximum element present in the array ARR

        int maxElement = Collections.max(arr);

    

        // Create an array distinctSubsets of size maxElement+1 with value 1 at each position

        ArrayList distinctSubsets = new ArrayList<>(maxElement + 1);

        for(int i=0 ; i        {

            distinctSubsets.add(1);

        }

    

        // Sort the array

        Collections.sort(arr);

    

        // Traverse through the array ARR

        for (int index = 0; index < n; index++) 

        {

            int element = arr.get(index);

    

            // Traverse through all the possible elements that we can insert in the subset

            for (int pos = 2 * element; pos <= maxElement; pos += element) 

            {

                distinctSubsets.set(pos , distinctSubsets.get(pos) + distinctSubsets.get(element));

            }

    

            // Increment totalSubsets by distinctSubsets[element]

            totalSubsets += distinctSubsets.get(element);

        }

    

        // Return the variable totalSubsets

        return totalSubsets;

	}



}

Python (3.5)

'''

   Time Complexity: O(N*Log(N) + Max(ARR)*Log(Max(ARR)))

   Space Complexity: O(Max(ARR))



   Where N is the number of elements in the array.

'''



def countGoodSubsets(arr):



    n = len(arr)



    # The variable totalSubsets stores the total number of good subsets

    totalSubsets = 0



    # The variable maxElement stores the maximum element present in the array ARR

    maxElement = max(arr)



    # Create an array distinctSubsets of size maxElement+1 with value 1 at each position

    distinctSubsets = [1 for j in range(maxElement + 1)]



    # Sort the array

    arr.sort()



    # Traverse through the array ARR

    for index in range(n):



        element = arr[index]



        # Traverse through all the possible elements that we can insert in the subset

        for pos in range(2 * element, maxElement + 1, element):



            distinctSubsets[pos] += distinctSubsets[element]



        # Increment totalSubsets by distinctSubsets[element]

        totalSubsets += distinctSubsets[element]



    # Return the variable totalSubsets

    return totalSubsets

C++ (g++ 5.4)

/*

   Time Complexity: O(N*Log(N) + Max(ARR)*Log(Max(ARR)))

   Space Complexity: O(Max(ARR))



   Where N is the number of elements in the array.

*/



#include



int countGoodSubsets(vector &arr) 

{

    int n = arr.size();



    // The variable totalSubsets stores the total number of good subsets

    int totalSubsets = 0;



    // The variable maxElement stores the maximum element present in the array ARR

    int maxElement = *max_element(arr.begin(), arr.end());



    // Create an array distinctSubsets of size maxElement+1 with value 1 at each position

    vector distinctSubsets(maxElement + 1, 1);



    // Sort the array

    sort(arr.begin(), arr.end());



    // Traverse through the array ARR

    for (int index = 0; index < n; index++) 

    {

        int element = arr[index];



        // Traverse through all the possible elements that we can insert in the subset

        for (int pos = 2 * element; pos <= maxElement; pos += element) 

        {

            distinctSubsets[pos] += distinctSubsets[element];

        }



        // Increment totalSubsets by distinctSubsets[element]

        totalSubsets += distinctSubsets[element];

    }



    // Return the variable totalSubsets

    return totalSubsets;

}

Accepted Answer

import java.util.Arrays;

public class CountGoodSubsets {

public static void main(String[] args) {

int[] ARR = {2, 3, 4, 6};

int result = countGoodSubsets(ARR);

System.out.println("Total number of good subsets: " + result);

}

public static int countGoodSubsets(int[] ARR) {

int N = ARR.length;

Arrays.sort(ARR); // Sort the array

int[] dp = new int[N];

Arrays.fill(dp, 1); // Initialize each element as a valid subset

int totalGoodSubsets = 0;

for (int i = 0; i < N; i++) {

for (int j = 0; j < i; j++) {

// Check if ARR[i] is divisible by ARR[j]

if (ARR[i] % ARR[j] == 0) {

dp[i] += dp[j];

}

totalGoodSubsets += dp[i];

}

return totalGoodSubsets;

}

For example :

Input Format :

Output Format :

Constraints :

Top Cloud Analogy Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Cloud Analogy Software Developer