## 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