Shivkumar - 1 year ago 53

Python Question

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 (

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

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

As

But how to do this

Also I am looking for a answer

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

Please help.

Thanks in Advance.

Answer Source

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