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:
- The first line should contain a Hexadecimal (base 16) number denoting the value of A’ .
- 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 # not found, return -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()
Reply