Reverse XOR: Cracking the Palindrome Code (Codeforces Problem)

When I first read the Reverse XOR problem on Codeforces, my instinct was to reach for a brute-force loop. After all, the task seems simple:

Does there exist a positive integer x such that x ⊕ reverse(x) = n?

Where reverse(x) means reversing the binary representation of x.
For example:

• x = 12 (1100₂) → reverse(x) = 3 (0011₂)

• 2 ⊕ 1 = 3

Brute force methods often struggle when dealing with large inputs that contain up to 10,000 or even millions of values. In these cases, the potential value can be as high as 2³⁰, making it impractical to check through all possible values iteratively.

In this post, I will walk through an optimal solution, explaining why it works and how it can be applied in real-world problem-solving scenarios.

🧠 Step 1: The Naïve Brute Force

With the starter code functions

def reverse_binary(n):
    return int(bin(n)[2:][::-1], 2)

def solve(n):
    max_x = min(n + 1000, 2**20)
    for x in range(1, max_x + 1):
        if x ^ reverse_binary(x) == n:
            return "YES"
    return "NO"

These current functions can process small numbers, but cause TLE issues on bigger test sets. This reveals a hidden structure within the XOR operation combined with reversal.

🪄 Step 2: Looking at Patterns

I debugged and displayed x ⊕ reverse(x) for different x values and looked for patterns in the binary strings.

x⊕reverse(x)=n

Suppose that the binary x has a length of k. Reversing the number mirrors the centre bits, implying that the number’s bit structure must mirror itself.

x       =  10010
reverse =  01001
xor     =  11011   ← palindrome

A rare case is when k is an odd number, when the middle bit is calculated by b_mid ⊕ b_mid = 0.

🧩 Step 3: Trailing Zeros

Leading zeros in reversed binary carry no significance and can be removed.

🧪 Step 4: The Final Efficient Solution

The following code block contains the final complete implementation.

import sys

def is_valid(n: int) -> bool:
    if n == 0:
        return True
    s = bin(n)[2:]
    a = s.rstrip('0')
    if a != a[::-1]:  # must be a palindrome
        return False
    if len(a) % 2 == 1 and a[len(a)//2] == '1':
        return False
    return True

def main():
    input = sys.stdin.readline
    t = int(input())
    out = []
    for _ in range(t):
        n = int(input())
        out.append("YES" if is_valid(n) else "NO")
    print("\n".join(out))

if __name__ == "__main__":
    main()

This is an efficient solution with an O(t) time complexity, enabling the application to process big data.