Divisible Set

Moderate
0/80
profile
Contributed by
60 upvotes
Asked in companies
UberNagarro SoftwareSoft Suave

Problem statement

You are given an array of distinct numbers ‘arr’ of size 'n'.


Your task is to return the largest subset of numbers from ‘arr’, such that any pair of numbers ‘a’ and ‘b’ from the subset satisfies the following: a % b == 0 or b % a == 0.


A subset is nothing but any possible combination of the original array


Example: 
Input: ‘arr’ = [1, 16, 7, 8, 4]

Output: [1, 4, 8, 16].

Explanation: In the set {1, 4, 8, 16}, you can take any pair from the set, and either one of the elements from the pair will divide the other.

There are other possible sets, but this is the largest one.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of each test case contains a single integer ‘n’ representing the number of elements in the array.

The second line of each test case contains ‘n’ space-separated integers representing the elements of the array.
Output Format:
Since there can be multiple possible answers, the Output will be "Correct" or "Incorrect" based on the validity of your answer.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
3
1 2 5
Sample Output 1 :
 Correct
Explanation of sample input 1:
The sets {1, 2} or {1, 5} are the two largest sets that satisfy the given condition.

Hence either of them could be the answer.
Sample Input 2:
 3
 3 3 3
Sample Output 2:
Correct
Explanation of sample input 2:
The set {3, 3, 3} is the largest set that satisfies the given condition.
Expected Time Complexity:
The expected time complexity is O(n^2).
Constraints:
1 <= N <= 5000
0 <= arr[i] <= 10^8    

Time Limit: 1 sec
Hint

 Try to solve this using a recursive approach

Approaches (3)
Brute Force

In this approach, we can see that for every element, we choose to either pick it or not pick it. An element can only be picked when it satisfies the condition in the question.


 

So, before picking any element, we need to check if either of the above two conditions satisfies each element already present in the current subset. But there's an important observation that allows us to optimise the above checking process. If the largest number in the subset formed till now divides the next element to be chosen, then every other element in the subset will divide it (because the subset formed till now follows the above conditions).

 

We create getMaxSubset(arr, start), where ‘start’ is the index of the current element to be inserted in the subset or not in the array ‘arr’. 

 

Algorithm:

  • In the function getMaxSubset(arr, start)
    • If start is not less than the length of arr, return an empty array
    • Create an empty array subSet
    • Iterate i from the start + 1 to the size of arr
      • If arr[i] % arr[start] equals 0, continue the loop
      • Set res as getMaxSubset(arr, i)
      • If the size of the res is not less than the size of ans set subSet as res
    • Insert arr[start] in subSet and return it.
  • In the given function
    • Sort the arr array
    • Create an empty array subSet
    • Iterate i from 0 to the size of arr
      • If arr[i] % arr[start] not equals 0, continue the loop
      • Set res as getMaxSubset(arr, i)
      • If the size of the res is not less than the size of ans set subSet as res
    • Return subSet
Time Complexity

O(n*(2^n)), Where n is the length of the array ‘arr’.
 

For each function call, we are making at most n different function calls, and it will take O(n) time to make a copy of each return array.

 

Hence the final time complexity is O(N*(2^N)).

Space Complexity

O(n), Where n is the length of the array.

 

The recursion stack will take at most as much space as the number of elements in the array.

 

Hence the final space complexity is O(n).

Code Solution
(100% EXP penalty)
Divisible Set
Full screen
Console