# Unpleasant Ones Codechef Solution

Page Contents

## Unpleasant Ones Solution Problem Code: UNONE

The ugliness of a string is defined as the count of two consecutive ones i.e. `"11"` in the given string. For example, the ugliness of string `"10111"` is 22.

You are given an array AA of NN integers and you have to find any ordering of the array such that the ugliness of the concatenated string of the binary representations of the integers (without leading zeros) is minimum.

### Input

• The first line of the input contains an integer TT denoting the number of test cases. Then TT test cases follow.
• The first line of each test case contains a single integer NN.
• The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

### Output

For each test case, output an ordering of AA such that the ugliness of the array is minimum. If there are multiple answers, you may output any.

### Constraints

• 1≤T≤10001≤T≤1000
• 1≤N≤10001≤N≤1000
• 1≤Ai≤1091≤Ai≤109

Subtask #1 (100 points): Original constraints.

### Sample Input

``````2
3
3 6 5
2
7 6
``````

### Sample Output

``````5 6 3
6 7
``````

### Explanation

Test Case 1: The binary representations of [5,6,3][5,6,3] are [101,110,11][101,110,11] and the concatenated string would be `"10111011"` which has ugliness 33. This is the minimum possible. [6,5,3][6,5,3] is also valid.

Test Case 2: The binary representations of [6,7][6,7] are [110,111][110,111] and the concatenated string would be `"110111"` which has ugliness of 33. This is the minimum possible. [7,6][7,6] is not valid as it has ugliness of 44.

Program:

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

int main(){
int t;
cin>>t;
vector <vector<int>> ans;
for(int i=0 ; i<t;i++){
int n;
cin >>n;
vector<int> v;
for(int j=0; j<n ;j++){
int x;
cin >>x;
v.push_back(x);
}
int k=v.size()-2;
while(v[v.size()-1]%2==0 && k>=0){
swap(v[k],v[v.size()-1]);
k--;
}
ans.push_back(v);
}
for(auto x:ans){
for(auto y:x){
cout << y << " ";
}
cout << endl;
}
return 0;
}``````