Subset GCD
Practice
0 (0 votes)
Medium
Problem
68% Success 199 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Mahima had a sequence of N integers. She generated all possible non-empty subsets of the array and found Greatest Common Divisor of elements in every subset. Thus, she formed a new sequence 2N -1 integers. But unfortunately, she lost the original sequence.

For example, if she intially had the sequence {1,2,4} then the GCD of  7 subsets are {1,1,1,1,2,2,4}. 

You are given the new sequence of  2N-1 integers in any random order.

Help her recover the original sequence.

Input Format

The first line contains a single integer  N.

Next line contains 2N-1 integers where every integer is the gcd of a subset of the original sequence. 

Output format

Print the original sequence in non-decreasing order.

 

Input Constraints :

1<=N<=20

1<=A[i]<=109

Probelm setter: Harshit Agarwala

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
6 votes
Tags:
SetsC++ObservationBasic MathMath
Editorial

Login to unlock the editorial