Problem title
Difficulty
Avg time to solve

Selecting Three People
Moderate
25 mins
Faulty Key
Moderate
25 mins
Sum of Big integers.
Easy
15 mins
Find the elements value if present in the cache.
Hard
35 mins
Combination Sum
Hard
45 mins
Apple Pickup
Hard
15 mins
XML encoding
Moderate
15 mins
Count Of 3s
Moderate
25 mins
Ninja and Binary Tree
Moderate
25 mins
Kevin and the tower of coins
Moderate
25 mins

Divisible Set

Difficulty: MEDIUM
Contributed By

Problem Statement

You are given an array of distinct numbers ‘arr’. 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.

For Example:
You are given ‘arr’ = [1, 16, 7, 8, 4] as you can the set {1, 4, 8, 16}, here you can take any pair from the set and either one of the elements from the pair will divide the other.
Input Format:
The first line of input contains a single integer ‘T’ representing the number of test cases.

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:
For each test case, print all set elements in a space-separated manner.

Print a separate line for each test case.
Constraints:
1 <= T <= 10
1 <= N <= 10^3
0 <= arr[i] <= 10^8    

Time Limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function. 
Sample Input 1:
2
5
1 16 7 8 4
3
1 2 5
Sample Output 1 :
 1 4 8 16
 1 2
Explanation:
For the first test case, ‘arr’ = [1, 16, 7, 8, 4] as you can the set {1, 4, 8, 16}, Here you can take any pair from the set and either one of the elements from the pair will divide the other. Hence it is the answer.

For the second test case, ‘arr’ = [1, 2, 5] as you can the with the set {1, 5} or {1, 2} can satisfy the given condition. Hence either of them could be the answer.
Sample Input 2:
 2
 1
 5
 3
 3 3 3
Sample Output 2:
5
3 3 3 
Reset Code
Full screen
copy-code
Console