Shivkumar Shivkumar - 7 days ago 6
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
ad = []
for i in comb:
x = bin(i[0])[2:].count('1')+bin(i[1])[2:].count('1')
ad.append(x)
# print ad
print max(ad)


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.

Please help.

Thanks in Advance.

Answer

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