## Problem: A or B

*Difficulty: Medium
Consider four numbers: A, B, C, and K. You must change at most K bits in A and B to form the numbers A’ and B’ satisfying the equation A’ | B’ = C. Here, the | symbol denotes the bitwise OR operation.

Given Q sets of the numbers defined above, find and print the respective values of A’ and B’ on new lines; if no such value exists, print -1 instead. If there are multiple solutions, make A’ as small as possible; if there are still multiple solutions, make B’ as small as possible.

Notes:

• A, B and C are given in Hexadecimal (base 16), and K is given in decimal (base 10).
• If the number of bits changed in A is kA and the number of bits changed in B is kB , then kA + kB must be <= K.

Input Format

The first line contains an integer, Q , denoting the number of queries. The subsequent lines describe each respective query as follows:

• The first line contains a single integer denoting the value of K.
• Each of the next 3 lines contains a Hexadecimal (base 16) number describing the respective values of A, B, and C.

Constraints

Output Format

Print two lines of output for each query:

1. The first line should contain a Hexadecimal (base 16) number denoting the value of A’ .
2. The second line must contain a Hexadecimal (base 16) number denoting the value of B’.

If no valid answer exists, you must instead print one line of output with the integer -1.

Note: The letters in Hexadecimal numbers must be in uppercase.

Sample Input

3
8
2B
9F
58
5
B9
40
5A
2
91
BE
A8


Sample Output

8
58
18
42
-1


Explanation

Query 0:
In this query, K = 8.
Change to A = 2B(16) to A’ = 8(16). 3 bits are changed.

Change B = 9F(16) to B’= 58(16) . 5 bits are changed.

Query 1:
In this query, K = 5.
Change A = B9(16) to A’ = 18(16). 3 bits are changed.
Change B = 40(16) to B’ = 42(16). Only 1 bit is changed.

Query 2:
There is no valid answer, so we print -1.

Approach:

There are two parts of the solution. The first is the one that I figured out, but I sucked at the second part.
Let’s me explain. The solution complexity is O(n).
Part 1: Convert A,B,C to binary, and equalize their length (calculate max length, then append 0 before the ones that are shorter). Traverse through each bit in C.
If C[i] == 0:
+ if A[i] = 1 => A[i] = 0, reduce K by 1
+ if B[i] = 1 => B[i] = 0, reduce K by 1
If C[i] == 1:
+ if A[i] == 0 and B[i] == 0 => B[i] = 1, reduce K by 1
While iterating through C, if K == 0 but still not A’ | B’ = C, then return -1
Note: in case C[i] == 1, we let B[i] = 1 since we want to minimize A first.

Part 2: Since not fully understood the description of the problem (my bad English), I had to see the tutorial, which then made me surprised. The second part when we minimize even further A. If K still bigger than 0.
i -> 0
while K > 0:
if C == [1]: # since if C[i] == 0 we cant change anything
+ if A[i] == 1 and B[i] == 1 => A[i] = 0 #minimize A, reduce K by 1
+ if A[i] == 1 and B[i] == 0 => A[i] = 0 and B[i] = 1, reduce K by 2

That’s it. How silly I am 😦

Implementation: Python 2.7

def figureOut(A, B, C, K):
# convert from base 16 to base 10
# in binary format
A = bin(int(A, 16))[2:]
B = bin(int(B, 16))[2:]
C = bin(int(C, 16))[2:]
maxLength = max(len(A), len(B), len(C))

#equalize A,B,C length
if len(A) < maxLength:
A = '0'*(maxLength-len(A)) + A
if len(B) < maxLength:
B = '0'*(maxLength-len(B)) + B
if len(C) < maxLength:
C = '0'*(maxLength-len(C)) + C
A, B, C = list(A), list(B), list(C)

# 1. found result
result = []
for i in range(len(C)):
if C[i] == '0':
if A[i] == '1':
A[i] = '0'
K -= 1
if B[i] == '1':
B[i] = '0'
K -=1
elif C[i] == '1':
if A[i] == '0' and B[i] == '0':
B[i] = '1'
K -= 1
if K < 0:
return -1

# found result,
# minimize A
i = 0
while K > 0:
if C[i] == '1':
if A[i] == '1' and B[i] == '1':
A[i] = '0'
K -= 1
elif A[i] == '1' and B[i] == '0':
if K > 1:
A[i] = '0'
B[i] = '1'
K -= 2

i += 1
if i == len(C):
break

return '{:X}'.format(int(''.join(A), 2)), '{:X}'.format(int(''.join(B), 2))

def main():
t = input()
for _ in range(t):
K = input()
A = raw_input().strip()
B = raw_input().strip()
C = raw_input().strip()

result = figureOut(A, B, C, K)
if result != -1:
print result[0]
print result[1]
else:
print -1

if __name__ == '__main__':
main()