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

Advertisements