Shivkumar - 1 year ago 76
Python Question

# To find the max( sum(count(set bits ) ) ) in any k-elements from the given list

I have a problem to find the max of sum of count of set bits in any k-elements from the given list.

Given :

``````n = 4   # length of list
k = 2   # choose only k elements of list whose count(sum(set bits)) is max
list  l= 6 2 1 0
``````

so If I choose numbers 6 (110) and 1 (001) with 2 and 1 set bits respectively, adding them gives me max count of set bits i.e . 3

What I tried is :

``````from itertools import combinations
s = list(map(int,raw_input().split()))
n = s[0]
k = s[1]

l = list(map(int,raw_input().split()))

comb = list(combinations(l, k))
# print comb
for i in comb:
x = bin(i[0])[2:].count('1')+bin(i[1])[2:].count('1')
``````

My problem is with line :

``````x = bin(i[0])[2:].count('1')+bin(i[1])[2:].count('1')
``````

As k = 2, I took this manually i[0] and i[1].
But how to do this dynamically.

Also I am looking for a answer without using list comprehension,as my list size may vary to 2 to 10^18 which cause memory exceeding.

If you can suggest any other logic,that will be much useful.

I would expect that there is a sort in there. I really think that combinations isn't needed because only the the items with the most bits set can make up the result. Consider the following:

Given your input, the following I think computes the result:

``````n = 4   # length of list
k = 2   # choose only k elements of list whose count(sum(set bits)) is max
l = [6, 2, 1, 0]
``````

like this:

``````>>> sorted(l, key=lambda v: bin(v)[2:].count('1'), reverse=True)[:2]
[6, 2]
``````

This can be made to stream over the input by using a heapq of size `k` and inserting `(bin(v)[2:].count('1'), v)` then the result can be product by extracting the numbers. The `heapq` function `nlargest` will work nicely

``````>>> import heapq
>>> heapq.nlargest(k, l, key=lambda v: bin(v)[2:].count('1'))
[6, 2]
``````

Note that `l` can be a iterator. This operates in constant space. The memory usage depends on `k` not on the length of the iterator.

Then you can compute the sum of the bits set as in the other answers:

``````>>> sum(bin(v)[2:].count('1') for v in [6,2])
3
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download