Mayank Pathak Mayank Pathak - 10 months ago 46
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')
for k, v in r.items():
if len(v) == 0:
for j in range(0, len(v)):
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()]
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 Source

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