# Please help me to identify the reason of WA for this code

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=[0]*30
ans=[0]*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[0]))
# print(x)
i=0
while k>0:
k-=1
ans[29-x[i][1]]=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[0]))
``````

Needed to be changed to:

``````x=sorted(x,key=lambda x:(-x[0],x[1]))
``````

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