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
answer is 3
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
@supplexcity it would be great if you explain your approach a bit …its hard to just dive into code and start to debug. (Also mention what all variables you used for what purpose).
1 Like