Interesting Sequence (Codeforces 1775C)
Tags: Math, bitmasks

Petya and his friend, robot Petya++, like to solve exciting math problems.One day Petya++ came up with the numbers $$$n$$$ and $$$x$$$ and wrote the following equality on the board: $$$$$$n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,$$$$$$ where $$$\&$$$ denotes the bitwise AND operation. Then he suggested his friend Petya find such a minimal $$$m$$$ ($$$m \ge n$$$) that the equality on the board holds.Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer.Can you solve this difficult problem?  

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2000$$$). The description of the test cases follows.The only line of each test case contains two integers $$$n$$$, $$$x$$$ ($$$0\le n, x \le 10^{18}$$$).

Output: For every test case, output the smallest possible value of $$$m$$$ such that equality holds.If the equality does not hold for any $$$m$$$, print $$$-1$$$ instead.We can show that if the required $$$m$$$ exists, it does not exceed $$$5 \cdot 10^{18}$$$.

Note: In the first example, $$$10\ \&\ 11 = 10$$$, but $$$10\ \&\ 11\ \&\ 12 = 8$$$, so the answer is $$$12$$$.In the second example, $$$10 = 10$$$, so the answer is $$$10$$$.In the third example, we can see that the required $$$m$$$ does not exist, so we have to print $$$-1$$$.

Sample Inputs:
5
10 8
10 10
10 42
20 16
1000000000000000000 0

Sample Outputs:
12
10
-1
24
1152921504606846976

Solution (Python):
import sys
input = lambda : sys.stdin.readline()
_0x3f = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
    (n, x) = _0x3f()

    def solve(n, x):
        if n == x:
            return n
        if x == 0:
            return 1 << n.bit_length()
        v = n
        while v & n and v & n != x:
            v += v & -v
        return v if v & n else -1
    print(solve(n, x))

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, x) = readInts()
    if n == x:
        return n
    elif n < x:
        return -1
    elif x == 0:
        m = len(bin(n)[2:])
        return int('1' + '0' * m, 2)
    else:
        (S1, S2) = (bin(n)[2:], list(bin(x)[2:]))
        (u, v) = (len(S1), len(S2))
        if u != v:
            return -1
        (t, done) = (True, 0)
        for i in range(1, u):
            if S2[i] != S1[i]:
                if S2[i] == '1':
                    t = False
                elif S2[i] == '0' and (not done):
                    done = 1
                    if S2[i - 1] != '0':
                        t = False
                    S2[i - 1] = '1'
            if done and S2[i] == '1':
                t = False
        return int(''.join(S2), 2) if t else -1
for _ in range(int(input())):
    print(solve())

Solution (Python):
def cf1775C():
    (n, x) = map(int, input().split())
    if n == x:
        print(n)
        return
    while n > x:
        lb = n & -n
        n ^= lb
        if n == x and n & lb << 1 == 0:
            print(n | lb << 1)
            return
    print(-1)
    return
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        cf1775C()