We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Bit Manipulation
  4. A or B
  5. Discussions

A or B

  • mryo531
     + 0 comments

    Simple python solution that follows the methodology described by the editorial

    Note: My initial implementation used masks to read and set the bits, but I found this wasn't fast enough for the last 3 tests. Converting to an array and accessing the bits by index proved to be much faster.

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'aOrB' function below.
#
# The function accepts following parameters:
#  1. INTEGER k
#  2. STRING a
#  3. STRING b
#  4. STRING c
#

def aOrB(k, a, b, c):
    # Write your code here
    a_arr = [int(i) for i in bin(int(a, 16))[2:]]
    b_arr = [int(i) for i in bin(int(b, 16))[2:]]
    c_arr = [int(i) for i in bin(int(c, 16))[2:]]
    
    a_mod = 4 - len(a_arr) % 4
    b_mod = 4 - len(b_arr) % 4
    c_mod = 4 - len(c_arr) % 4
    if a_mod < 4:
        a_arr[:0] = [0] * a_mod
    if b_mod < 4:
        b_arr[:0] = [0] * b_mod
    if c_mod < 4:
        c_arr[:0] = [0] * c_mod

    swap = 0
    for i in range(len(c_arr)):
        if c_arr[i]:
            if not a_arr[i] and not b_arr[i]:
                b_arr[i] = 1
                swap += 1
        else:
            if a_arr[i]:
                a_arr[i] = 0
                swap += 1
            if b_arr[i]:
                b_arr[i] = 0
                swap += 1

        if swap > k:
            print(-1)
            return
    
    left_over = k - swap
    for i in range(len(c_arr)):
        if left_over == 0:
            break
            
        if a_arr[i]:
            if b_arr[i]:
                a_arr[i] = 0
                left_over -= 1
            elif left_over >= 2:
                a_arr[i] = 0
                b_arr[i] = 1
                left_over -= 2
    
    a = int(''.join([str(i) for i in a_arr]), 2)
    b = int(''.join([str(i) for i in b_arr]), 2)
    print(hex(a)[2:].upper())
    print(hex(b)[2:].upper())
        

if __name__ == '__main__':
    q = int(input().strip())

    for q_itr in range(q):
        k = int(input().strip())

        a = input()

        b = input()

        c = input()

        aOrB(k, a, b, c)