Competitive Coding - Mask bits - Decimal to Binary

Question

I am trying to solve a competitive coding problem. I managed to pass all the test cases except one. I am guessing that I've missed some kind of an edge case.

Problem:

Given a decimal number as input, convert it to binary and change the bits at the specified positions(given in the input) in the binary form of the number to 0. Output the resulting binary number in decimal form.

Here is my code:

import math
for _ in range(int(input())):
    n = int(input()) #The given number
    a = list(map(int, input().split())) #Positions at which the bits need to be masked
    b = str(bin(n))[:1:-1]
    for i in a:
        if i<=len(b) and b[i-1]=='1':
            n-=math.pow(2, i-1)
    print(int(n))

If somebody could tell the possible edge cases that I might have missed, it would be great. I couldn't find any sort of discussion for this problem and it does not allow me to see other's solution. Any help is appreciated. Thanks.

I did take into consideration the mask positions being higher than the number of bits. Still couldn't pass the test case. :( — Ankita
– Ankita, Commented Oct 7, 2018 at 11:46
I just wrote some test code (using bitwise operations), and your code worked correctly in all my trials. So I guess the corner cases involve negative numbers, or zeroes in the a list. — PM 2Ring
– PM 2Ring, Commented Oct 7, 2018 at 13:17
I forgot to mention the constraints! 1 ≤ T ≤ 104, 1 ≤ N ≤ 2^(32)-1, 1 ≤ Size(A) ≤ 32, 1 ≤ Ai ≤ 32, A position Ai occurs only once in the array A. So there's no need to handle negative integers. Since they have given 1 ≤ Ai ≤ 32, would I be right in assuming that there won't be a test case where there are no changes made? — Ankita
– Ankita, Commented Oct 7, 2018 at 13:18
1 ≤ Size(A) ≤ 32 does indicate that A will always have at least 1 element. And 1 ≤ Ai ≤ 32 means you don't have to worry about A containing zero. So at this point, I don't know what to suggest. — PM 2Ring
– PM 2Ring, Commented Oct 7, 2018 at 13:21

PM 2Ring · Accepted Answer · 2018-10-07 13:38:53Z

1

I can't find any corner cases that your code doesn't handle correctly, assuming the conditions you mention in the comments apply to the test data. But here's a more efficient version of that algorithm, using bitwise operations. Not only is it faster, it also handles the case of zero in the bit mask list, although that should not be an issue.

for _ in range(int(input())):
    # The given number
    n = int(input())
    # Create the bit mask
    mask = sum(1 << int(u) for u in input().split()) >> 1
    # Invert the bits in n which are also in mask
    n ^= n & mask
    print(n)

answered Oct 7, 2018 at 13:38

PM 2Ring

55.6k6 gold badges96 silver badges202 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Competitive Coding - Mask bits - Decimal to Binary

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related