Codeforcess solution 1385-B B. Restore the Permutation by Merger ,C++, Java, Js and Python

Algorithm

A permutation of length $n$ is a sequence of integers from $1$ to $n$ of length $n$ containing each number exactly once. For example, $[1]$ , $[4, 3, 5, 1, 2]$ , $[3, 2, 1]$ are permutations, and $[1, 1]$ , $[0, 1]$ , $[2, 2, 1, 4]$ are not.

There was a permutation $p [1 \dots n]$ . It was merged with itself. In other words, let's take two instances of $p$ and insert elements of the second $p$ into the first maintaining relative order of elements. The result is a sequence of the length $2 n$ .

For example, if $p = [3, 1, 2]$ some possible results are: $[3, 1, 2, 3, 1, 2]$ , $[3, 3, 1, 1, 2, 2]$ , $[3, 1, 3, 1, 2, 2]$ . The following sequences are not possible results of a merging: $[1, 3, 2, 1, 2, 3$ ], [ $3, 1, 2, 3, 2, 1]$ , $[3, 3, 1, 2, 2, 1]$ .

For example, if $p = [2, 1]$ the possible results are: $[2, 2, 1, 1]$ , $[2, 1, 2, 1]$ . The following sequences are not possible results of a merging: $[1, 1, 2, 2$ ], [ $2, 1, 1, 2]$ , $[1, 2, 2, 1]$ .

Your task is to restore the permutation $p$ by the given resulting sequence $a$ . It is guaranteed that the answer exists and is unique.

You have to answer $t$ independent test cases.

Input

The first line of the input contains one integer $t$ ( $1 \leq t \leq 400$ ) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ( $1 \leq n \leq 50$ ) — the length of permutation. The second line of the test case contains $2 n$ integers $a_{1}, a_{2}, \dots, a_{2 n}$ ( $1 \leq a_{i} \leq n$ ), where $a_{i}$ is the $i$ -th element of $a$ . It is guaranteed that the array $a$ represents the result of merging of some permutation $p$ with the same permutation $p$ .

Output

For each test case, print the answer: $n$ integers $p_{1}, p_{2}, \dots, p_{n}$ ( $1 \leq p_{i} \leq n$ ), representing the initial permutation. It is guaranteed that the answer exists and is unique.

Example
input
Copy
5
2
1 1 2 2
4
1 3 1 4 3 4 2 2
5
1 2 1 2 3 4 3 5 4 5
3
1 2 3 1 2 3
4
2 3 2 4 1 3 4 1
output
Copy
1 2 
1 3 4 2 
1 2 3 4 5 
1 2 3 
2 3 4 1 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

int main(){
  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    int arr[n];
    map<int, bool> inp;
    int x, k = 0;
    for(int i = 0; i < 2*n; i++){
      cin>>x;
      if(!inp[x]){
        arr[k] = x;
        inp[x] = true;
        k++;
      }
    }
    for(int i = 0; i < n; i++){
      cout<<arr[i]<<" ";
    }
    cout<<endl;
  }
}

Copy The Code & Try With Live Editor

Input

–

cmd

5
2
1 1 2 2
4
1 3 1 4 3 4 2 2
5
1 2 1 2 3 4 3 5 4 5
3
1 2 3 1 2 3
4
2 3 2 4 1 3 4 1

Output

–

cmd

1 2
1 3 4 2
1 2 3 4 5
1 2 3
2 3 4 1

Demonstration

Codeforcess solution 1385-B B. Restore the Permutation by Merger ,C++, Java, Js and Python,1385-B,Codeforcess solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 479 0