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()))
    w=[i for i in range(29,-1,-1)]
    # print(w)
    for i in range(n):
    # print(*bins)
    for i in range(30):
        for j in range(n):
            if bins[j][i]=="1":
    x=sorted(x,key=lambda x:(-x[0]))
    # print(x)
    while k>0:
    ans="".join(str(i) for i in ans)
    # print(ans)

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:

2 1
6 2

neither for this case
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. :grin:

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?

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. :grin:

1 Like

please help me as well in same problem

@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