Mayank Pathak - 6 months ago 33

Python Question

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]`

The answer should be

`[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.

Answer

`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())`

.

In any case I see no use for a dictionary for this. This should suffice:

```
sorted(A, key=lambda i: bin(i).count('1'))
```