monk-and-tasks

Monk A loves to complete all his tasks just before the deadlines for introducing unwanted thrill in his life. But, there is  another Monk D who hates this habit of Monk A and thinks it's risky. 

To test Monk A, Monk D provided him tasks for N days in the form of an array Array, where the elements of the array represent the number of tasks.

The number of tasks performed by Monk A on the i^th day is the number of ones in the binary representation of Arrayi.   

Monk A is fed up of Monk D, so to irritate him even more, he decides to print the tasks provided in non-decreasing order of the tasks performed by him on each day. Help him out!

Input:
The first line of input contains an integer T, where T is the  number of test cases.
The first line of each test case contains N, where N is the number of days.
The second line of each test case contains Array array having N elements, where Arrayi represents the number of tasks provided by Monk D to Monk A on i^th day.  

Output:
Print all the tasks provided to Monk A in the non-decreasing order  of number of tasks performed by him.    

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10^5
1 ≤ Arrayi ≤ 10^18

Note:
If two numbers have the same number of ones (set bits), print the one which came first in the input first, and then the other one, as in the input.

SAMPLE INPUT
1
4
3 4 7 10

SAMPLE OUTPUT
4 3 10 7

Explanation

In the sample input, T = 1 and N = 4, where N is the number of days.  

Tasks provided to Monk A on first day is  3 and binary representation of 3 is { 11 }2,  which contains 2 ones.   

Tasks provided to Monk A on second day is  4  and binary representation of 4 is { 100 }2,  which contains 1 ones.   

Tasks provided to Monk A on third day is 7 and binary representation of 7 is { 111 }2,  which contains 3  ones.   

Tasks provided to Monk A on fourth day is 10 and binary representation of 10 is { 1010 }2,  which contains 2 ones.  

So the Output will be:
4 3 10 7

Difficulty: EASY
Tags: String algorithms

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

from collections import OrderedDict

T = int(input())

def get_no_of_ones(n):
	count = 0
	while(n):
		n = n & (n-1)
		count += 1
	return count

for _ in range(T):
	op = []
	dic=OrderedDict()
	N = int(input())
	li = input().split(" ")
	for t in li:
		op.append((t, get_no_of_ones(int(t))))
	sorted_li = sorted(op, key=lambda x:x[1])
	for key in sorted_li:
		print(key[0], end=' ')
	print("")
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name

print 'Hello World!'
'''

from collections import OrderedDict
from operator import itemgetter
def countsetbits(n):
	count = 0
	while (n):
		if (n&1):
			count = count + 1
		n = n >> 1
	return count

def functionprint(d):
	for k in d.keys():
		print(k, end=' ')
t = int(input())


ans = []
while (t):
	n = int(input())
	list = list(map(int, input().strip().split()))
	for i in list:
		count = countsetbits(i)
		ans.append((i,count))
#        print count
	ans = sorted(ans, key= lambda tup: tup[1])
	for k,v in ans:
		print(k, end=' ')
	print('')
#    print d.keys()
	ans[:] = []
	t = t - 1


from operator import itemgetter

t = int(input())

for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	binarr = []
	for elem in arr:
		temp = str(bin(elem))
		binarr.append((elem, temp.count('1')))
	binarr.sort(key=itemgetter(1))
	ans = ''
	for elem in binarr:
		ans += str(elem[0]) + ' '
	print(ans)


for _ in range(eval(input())):
	_ = eval(input())
	arr = list(map(int, input().split()))
	arr = [(bin(i).count('1'), i) for i in arr]
	arr.sort(key=lambda x: x[0])
	for bi, val in arr:
		print(val, end=' ')
	print("")


def yo(x):
	return str(bin(x)).count('1')

for _ in range(int(input())):
	
	n = int(input())
	
	l = [int(i) for i in input().strip().split(" ")]
		

	l = sorted(l, key=yo)

	for i in l:
		print(i, end=' ')

	print()


def bitcount(n):
    
	count = 0
	while n > 0:
		count = count + 1
		n = n & (n-1)
	return count 


for _ in range(int(input())):
	
	n = int(input())
	
	l = [int(i) for i in input().strip().split(" ")]
	d = {}
	for i in l:
		a = i
		#cnt = 0
		# Counting number of set bits.
		#while i>0:	
		#	cnt+=1
		#	i = i&(i-1)
		#print cnt
		cnt = bitcount(i)
		if d.get(cnt, 0):
			d[cnt].append(a)
		else:
			d[cnt] = [a]
		

	
	for i in sorted(d.keys()):
		for k in d[i]:
			print(k, end=' ')
	
		
	print()


def bitcount(n):
    
	count = 0
	while n > 0:
		count = count + 1
		n = n & (n-1)
	return count 
for _ in range(int(input())):
	lis=[]
	dict={}
	n=int(input())
	lis=[int(i) for i in input().split()]
	for p in lis:
		s=bitcount(p)
		if dict.get(s):
			dict[s].append(p)
		else:
			dict[s]=[p]
	for key in sorted(dict.keys()):
		for o in dict[key]:
				print((o), end=' ')
		
	print();        




#t = int(raw_input())

#while t:
#	t-=1
#	
#	n = int(raw_input())
#	
#	l = map(int, raw_input().strip().split(" "))
#	
#	for i in l:
#		a = i
#		cnt = 0
#		# Counting number of set bits.
##			cnt+=1
#			i = i&(i-1)
#		#print cnt
#		
#		if d.get(cnt, 0):
#			d[cnt].append(a)
#		else:
#			d[cnt] = [a]
#		
#
#	
#	for i in sorted(d.keys()):
#		for k in d[i]:
#			print k,
#	
#		
#	print


# -*- coding: utf-8 -*-
"""
Created on Mon Sep 05 12:40:57 2016

@author: acer
"""


def binary(num):
	ret=0
	while (num!=0):
		bit=num%2
		if bit==1:
			ret=ret+1
		num=num/2
	return ret
		
	
l=int(input())
for t in range(0,l):
	n=int(input())
	a=[]
	m={}
	out=[]
	a = [int(z) for z in input().split()]
	for i in range(0,n):
		j=binary(a[i])
		m[j]=[]
	
	for i in range (0,len(out)):
		m[out[i]]=[]
	for i in range (0,n):
		j=binary(a[i])
		m[j].append(a[i])
	keylist = list(m.keys())
	keylist.sort()
	out=[]
	for key in keylist:
		out=out+m[key]
	
	
	print (*out)
		


from sys import stdin, stdout 

def comparar(a,b):
	xa=bin(a)[2:].count('1')
	xb=bin(b)[2:].count('1')
	if xa == xb:
		return 0
	elif xa<xb:
		return -1
	else:
		return 1
	
T = int(input())

for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	A.sort(comparar)
	for j in A:
		stdout.write(str(j)+" ")
	stdout.write("\n")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
	
for _ in range(eval(input())):
	res = []
	final = []
	number_of_tasks = eval(input())
	tasks = [int(x) for x in input().split()]
	
	for i in range(number_of_tasks):
		res.append((i, "{0:b}".format(tasks[i]).count('1')))
	
	ans = sorted(res, key=lambda x: x[1])
	for k, v in ans:
		final.append(tasks[k])
	print(" ".join(str(x) for x in final))


def count_bits(n):
	cnt = 0
	while n:
		cnt += n & 1
		n = n >> 1
	return cnt


def count_tasks(numbers):
	res = {}

	for n in numbers:
		no_bits = count_bits(n)
		if no_bits in res:
			lst = res[no_bits]
		else:
			lst = []
		lst.append(n)
		res[no_bits] = lst
	return res


def solve(numbers):
	res = count_tasks(numbers)
	sorted_res = []
	for k in sorted(res):
		sorted_res += res[k]
	print(" ".join(str(s) for s in sorted_res))


def execute():
	n = int(input())

	while (n > 0):
		input()
		numbers = list(map(int, input().split()))
		solve(numbers)
		n -= 1

execute()


def countsetbits(n):
	setbits=0
	while n:
		n&=(n-1)
		setbits+=1
	return setbits

t=int(input())
while t:
	t-=1
	s=[0]*100
	for i in range(100):
		s[i]=[]
	n=int(input())
	l=[int(i) for i in input().split()]
	for i in l:
		setb=countsetbits(i)
		s[setb].append(i)
	for i in range(100):
		if(len(s[i])>0):
			for j in s[i]:
				print(j, end=' ')
	print()


# Weird Python
# Making function makes code to run faster.
# http://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function
# Due to array lookup in python instead of dict lookup for python global vars.
def bitcount(n):
    
	count = 0
	while n > 0:
		count = count + 1
		n = n & (n-1)
	return count 


def make_dict(l):
	d = {}
	for i in l:
		cnt = bitcount(i)
		if d.get(cnt, 0):
			d[cnt].append(i)
		else:
			d[cnt] = [i]
	return d

for _ in range(int(input())):
	
	n = int(input())
	
	l = [int(i) for i in input().strip().split(" ")]
		
	d = make_dict(l)
	
	for i in sorted(d.keys()):
		for k in d[i]:
			print(k, end=' ')

	print()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

t = int(input())
for _ in range(t):
	n = int(input())
	print(" ".join(map(str, sorted(map(int,input().split()), key=lambda x: bin(x)[2:].count("1")))))


b=[]
for _ in range(eval(input())):
	b=[]
	n=eval(input())
	a=list(map(int,input().split()))
	c=[i for i in range(n)]
	for i in range(len(a)):
		b.append(bin(a[i]).count("1"))
	for i in [x for (y,c,x) in sorted(zip(b,c,a))]: print(i, end=' ')
	print() 
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

from operator import itemgetter

def countOnes(work):
	count = 0
	while(work):
		work = (work&(work-1))
		count +=1
	return count
	
def monkTasks(workDays):
	workDays.sort(key=itemgetter(1))
	return workDays
	

try:
	testCase = int(input())
	while(testCase):
		workDays = []
		days = int(input())
		works = input().split()
		for work in works:
			workDays.append((int(work),countOnes(int(work))))
			days -= 1
		result = monkTasks(workDays)
		print((" ".join([str(item[0]) for item in result])))
		# for item in result:
		# 	print("%d " % item[0])
		# print '\n'
		testCase -= 1
except Exception as e:
	print(e.message)


from sys import stdin, stdout 

def comparar(a,b):
	xa=bin(a)[2:].count('1')
	xb=bin(b)[2:].count('1')
	if xa == xb:
		return 0
	elif xa<xb:
		return -1
	else:
		return 1
	
T = int(input())

for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	A.sort(comparar)
	for j in A:
		stdout.write(str(j)+" ")
	stdout.write("\n")


noOfTestCases = int(input())


def order(list1):
	# value : {index1: no1, index2: no2}
	countHash = {}
	for index, no in enumerate(list1):
		no = int(no)
		countOf1 = bin(no).count('1', 0, len(bin(no)))
		if(countOf1 in countHash):
			countHash[countOf1][index] = no
		else:
			countHash[countOf1] = {}
			countHash[countOf1][index] = no
	
	ans = []
	
	for i in sorted(countHash.keys()):
		sorted(countHash[i].keys())
		for j in  sorted(countHash[i].keys()):
			ans.append(str(countHash[i][j]))
	print(" ".join(ans))		
	

for i in range(1, noOfTestCases + 1):
	count = int(input())
	nos = input().split(" ")
	order(nos)


def count_bits(n):
	cnt = 0
	while n:
		cnt += n & 1
		n = n >> 1
	return cnt


def count_tasks(numbers):
	res = {}

	for n in numbers:
		no_bits = count_bits(n)
		lst = res.get(no_bits, [])
		lst.extend([n])
		res[no_bits] = lst
	return res


def solve(numbers):
	res = count_tasks(numbers)
	sorted_res = []
	for k in sorted(res):
		sorted_res += res[k]
	print(" ".join(str(s) for s in sorted_res))


def execute():
	n = int(input())

	while (n > 0):
		input()
		numbers = list(map(int, input().split()))
		solve(numbers)
		n -= 1

execute()


def count_bits(n):
	cnt = 0
	while n:
		cnt += n & 1
		n = n >> 1
	return cnt


def count_tasks(numbers):
	res = {}

	for n in numbers:
		no_bits = count_bits(n)
		lst = res.get(no_bits, [])
		lst.append(n)
		res[no_bits] = lst
	return res


def solve(numbers):
	res = count_tasks(numbers)
	sorted_res = []
	for k in sorted(res):
		sorted_res += res[k]
	print(" ".join(str(s) for s in sorted_res))


def execute():
	n = int(input())

	while (n > 0):
		input()
		numbers = list(map(int, input().split()))
		solve(numbers)
		n -= 1

execute()


def mySort(t,N):
	ele = [[] for i in range(61)]
	i = 0
	while(i<N):
		ele[bin(t[i]).count('1')].append(t[i])
		i = i + 1
	j = 1
	while(j<60):
		if(len(ele[j])>0):
			print(' '.join(map(str, ele[j])), end=' ')
		j = j+1
	print(' '.join(map(str, ele[60])))


T = int(input())
for q in range(T):
	N = int(input())
	t = list(map(int, input().split()))
	mySort(t,N)


def bin_sort(t, N):
	db = [[0] for x in range(64)] # empty list of lists
	i = 0
	while(i < N):
		b = bin(t[i]).count('1')
		db[b][0] += 1
		db[b].append(t[i])
		i += 1
	b = 0
	while(b < 64):
		if(db[b][0]):
			i, n = 0, db[b][0]
			while(i < n):
				print(db[b][i+1], end=' ')
				i += 1
		b += 1
	print()

T = int(input())
for q in range(T):
	N = int(input())
	t = list(map(int, input().split()))
	bin_sort(t, N)


def countsetbits(n):
	setbits=0
	while n:
		n&=(n-1)
		setbits+=1
	return setbits

for _ in range(int(eval(input()))):
	s=[0]*100
	for i in range(100):
		s[i]=[]
	n=int(input())
	l=[int(i) for i in input().split()]
	for i in l:
		setb=countsetbits(i)
		s[setb].append(i)
	for i in range(100):
		if(len(s[i])>0):
			for j in s[i]:
				print(j, end=' ')
	print()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
from operator import itemgetter
t = int(input())

while t!= 0:
	t = t-1
	n = int(input())
	data = list()
	array = list(map(int,input().split(' ')))
	
	for i in array :
		x = i
		count = 0
		while x!=0 :
			x = x & (x-1)
			count+=1
		data.append([count,i])
		
	data = sorted(data, key = itemgetter(0))
	
	for i in data :
		print(i[1], end=' ')
	
	print("")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

t = int(input())

while(t>0):
	n = int(input())
	inp = input().split(' ')
	a = list(map(int,inp))
	dic =[]
	i = 0
	while(i<len(a)):
		count = 0
		x = a[i]
		while(a[i]):
			a[i] = a[i] & (a[i]-1)
			count = count + 1
		dic.append((count,x))
		i = i + 1
	t = t - 1
	dic = sorted(dic,key=lambda x: x[0])
	for i in range(n):
		print(dic[i][1],end=' ')
	print(end = '\n')
	


noOfTestCases = int(input())


def order(list1):
	countHash = {}
	for index, no in enumerate(list1):
		no = int(no)
		countOf1 = bin(no).count('1', 0, len(bin(no)))
		if(countOf1 in countHash):
			countHash[countOf1][index] = no
		else:
			countHash[countOf1] = {}
			countHash[countOf1][index] = no
	
	order = ""
	
	sortedOuterKeys = sorted(countHash.keys())
	
	for i in sortedOuterKeys:
		sortedInnerKeys = sorted(countHash[i].keys())
		for j in  sortedInnerKeys:
			order += str(countHash[i][j]) + " "
			
	return order		
	

for i in range(1, noOfTestCases + 1):
	count = int(input())
	nos = input().split(" ")
	print(order(nos))