Unpleasant Ones Codechef Solution

by

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

Subtasks

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;
}

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

fifteen + 16 =