Given N, return M that satisfy the equation: N + M = 2 * (N XOR M)

Question

Problem

Given N, return M that satisfy the equation: N + M = 2 * (N ^ M)

Constraints

1 <= Test Cases = 10^5; 
1 <= N <= 10^18

I came across this problem in one of the hiring challenges.

By trial and error method, I have found a pattern that - Such an M exists between N/3 and 3N and that N + M is an Even number. So I code it up and upon submission, my solution only managed to pass only half of the test cases. This is not much of an optimisation as this method's time complexity is same as that of Brute force solution.

I know that my solution is not the Optimal solution.

Here's my solution:

def solve(n):
    m = n//3
    end = 3*n
    
    # If both m and n are odd/even, their sum will be even
    if (m&1 == 1 and n & 1 == 1) or (m&1 == 0 and n&1 == 0):
        inc = 2
    else:
        m += 1
        inc = 2

    while m <= end:
        if (n + m) == 2 * (n ^ m):
            return m

        m += inc

Could someone provide me some hints/methods/algorithm to get an Optimal Solution. Thanks!

Answer 1

The bottom bit of m is determined (since n+m must be even). Given that bottom bit, the next bit is determined, and so on.

That observation leads to this O(log n) solution:

def solve(n):
    b = 1
    m = 0
    while n + m != 2 * (n ^ m):
        mask = 2 * b - 1
        if ((n + m) & mask) != ((2 * (n ^ m)) & mask):
            m += b
        b *= 2
    return m

Another way to implement this is to find the smallest bit in which m+n and 2*(n^m) differ, and toggle that bit in m. That results in this very compact code (using the new walrus operator, and some bit-twiddling tricks):

def solve(n):
    m = 0
    while r := n + m ^ 2 * (n ^ m):
        m |= r & -r
    return m