Mayank Pathak - 3 years ago 121
Python Question

# How to find set bits of integers in an array and print the numbers in a non decreasing order of set bits

Question that i am trying to solve is

Given an array of integers print the array in non decreasing order of number of set bits of array elements and if two numbers have same number of set bits then print them in the order of their occurrence in the set bit

For eg if array is

``````A = [3, 4, 7, 10]
``````

``````[4, 3, 10, 7]
``````

Here is the python code that i am doing

``````import collections

def count_set_bits(a):
s = []
r = collections.defaultdict(list)
for i in a:
count = bin(i).count('1')
r[count].append(i)
for k, v in r.items():
if len(v) == 0:
continue
else:
for j in range(0, len(v)):
s.append(v[j])
return ' '.join(str(i) for i in s)

T = int(raw_input())
while T != 0:
N = int(raw_input())
A = [int(z) for z in raw_input().split()]
print(count_set_bits(A))
T -= 1
``````

It runs fine on most of the test data but is failing in particular test data like

``````[447426071, 11806879, 436454227, 805034980, 1166995993, 1613909963]
``````

My output is

``````[447426071, 11806879, 436454227, 805034980, 1166995993, 1613909963]
``````

The expected output is

``````[11806879, 436454227, 1166995993, 1613909963, 447426071, 805034980]
``````

I just want to know if the problem is related to the particular data structure i am using or is their any logical error i have made.

`defaultdict` does not have any order guarantees and you're not iterating over it in any order. Perhaps you meant to use `sorted(r.items())`.
``````sorted(A, key=lambda i: bin(i).count('1'))