Size of longest Divisible Subset in an Array in Java

In a given input array, the task is to find the size of the longest divisible subset. A subset is known as divisible only if, for each pair (p, q) in the subset, either p divides q (p % q = 0) or q divides p (q % p = 0).

Example 1:

Input

int arr[] = {1, 16, 7, 19, 28, 8, 4, 64, 256}

Output: 6

Explanation: Consider the subset {1, 16, 8, 4, 64, 256}. In this subset, we can make 15 (⁶C₂ = 15) pairs of elements. In any of the pairs (comprising of two elements, p and q), either p % q = 0 or q % p = 0. Also, the considered subset is the longest subset that satisfies the given condition, whose size is 6. Hence, the output is 6.

Example 2:

Input

int arr[] = {2, 2, 2, 2, 2, 2, 2}

Output: 7

Explanation: All the elements of the input array divide each other completely as, all the elements are of the same value. Therefore, the longest subset is the input array itself, whose size is 7. Hence, the output is 7.

Approach: Using Recursion

The simple approach is to generate all of the possible subsets from the given input array and then check whether the generated subsets are valid or not as per the given condition. If the subset is valid, then compare its size with the previously computed maximum size of the previously computed valid subset and update the answer accordingly. All of the subsets can be generated by excluding or including the current element in the current subset. We will be generating and validating the side of the subset by the side in the same method. Observe the following implementation.

FileName: LongestDivisibleSubset.java

Output:

For the input array: 
1 16 7 19 28 8 4 64 256 
The maximum size of the longest divisible subset is: 6


For the input array: 
2 2 2 2 2 2 2 
The maximum size of the longest divisible subset is: 7

Complexity Analysis: The program generates two recursive calls in each recursive call. It leads to exponential time complexity. Therefore, the time complexity of the program is O(2n). The array list that stores all of the subsets (subsetAL in our case) make the space complexity of the program exponential, which is also O(2n), where n is the total number of elements present in the input array.

The time, as well as the space complexity of the above program, is very high and is not suitable for larger inputs. Therefore, it is required to reduce both complexities.

Efficient Approach: Using Sorting

With the help of sorting, one can reduce the time as well the space complexity of the program. Observe the following steps.

Step 1: Sort all of the elements of the input array in ascending order. The reason for sorting is to ensure that all of the divisors of an element come before it.

Step 2: Create an array divisibleCount[] whose size is the same as the input array. divisibleCount[i] keeps the size of divisible subset ending with arr[i] (In the sorted array). The minimum value of divisibleCount [i] would be 1.

Step 3: Traverse all array elements. For every element, find a divisor arr[j] with the largest value of divisibleCount[j] and store the value of divisibleCount[i] as divisibleCount[j] + 1.

Observe the implementation of the above steps.

FileName: LongestDivisibleSubset1.java

Output:

For the input array: 
1 16 7 19 28 8 4 64 256 
The maximum size of the longest divisible subset is: 6


For the input array: 
2 2 2 2 2 2 2 
The maximum size of the longest divisible subset is: 7

Complexity Analysis: The program is using two nested-for loops, which makes the time complexity of the program O(n²). The program is also using auxiliary arrays for finding the result, which makes the space complexity of the program O(n), where n is the total number of elements present in the input array.