Mayank Pathak Mayank Pathak - 1 month ago 10
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]


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'))