 This code is in reference to the problem PROBLEM

``````for _ in range(int(input())):
n, k = map(int, input().split())
arr = list(map(int, input().split()))
bins=[]
bit=*30
ans=*30
w=[i for i in range(29,-1,-1)]
# print(w)
for i in range(n):
b=bin(arr[i])[2:]
bins.append("0"*(30-len(b))+b)
# print(*bins)
for i in range(30):
count=0
for j in range(n):
if bins[j][i]=="1":
count+=1
bit[i]=2**(29-i)*count
x=zip(bit,w)
x=sorted(x,key=lambda x:(-x))
# print(x)
i=0
while k>0:
k-=1
ans[29-x[i]]=1
i+=1
ans="".join(str(i) for i in ans)
# print(ans)
print(int(ans,2))
``````

It works for sample test cases and my personal test cases but gives WA.

My idea is to calculate the contribution of each bit and storing their contribution in list “bits”, then I sort them in reverse order of their contribution value, then finally I set the top k bits in the list “ans” for the result.

It doesn’t look like you’re doing anything when values for bits are tied (that is, it’ll be arbitrary, while the problem specifically wants the minimum number in that case)

Example countercase:

``````1
2 1
6 2
``````
3 Likes

neither for this case
1
4 2
2 2 2 2

1 Like

Thanks, @galencolin, and @raghav_3018 for giving the test cases. I got my mistake. I was not sorting the value if there are more than two numbers which give the same sum with the same number of set bits.
To be precise:

``````x=sorted(x,key=lambda x:(-x))
``````

Needed to be changed to:

``````x=sorted(x,key=lambda x:(-x,x))
``````

It’s now accepted. The k bits the are set in our answer need to be in those positions which have the maximum occurrences of a set bit right?

@arujbansal1
Not the maximum in occurrences but maximum in the place value.
You can have 5 set bits at 2^0 (right most) place but their combined value is less than the 1 bit set at 2^3 (4th from right) place so our priority will be to set the 1 bit at 2^3 place rather than the bit at the 2^0 place.
Hope you get it.
Cheers. 1 Like