Maximum XOR - Microsoft Online Assessment

Problem Preview

"Given an integer `n` such that `n` is divisible by `4`, find an integer `x` satisfying: - `n ≤ x < 2n` - `x` has the same bit-length as `n` Define: `v = n ⊕ (n + 1) ⊕ (n + 2) ⊕ ... ⊕ x` where `⊕` denotes the **bitwise XOR** operation. Your task is to choose `x` such that `v` is **maximum**. If multiple values of `x` produce the same maximum value of `v`, return the **smallest** such `x`. ## Examples | n | Answer | |---:|---:| | 4 | 6 | | 8 | 14 | | 12 | 14 | ### Example 1 For `n = 4`: ```text 4 ⊕ 5 ⊕ 6 = 7 The maximum is achieved at: x = 6 Example 2 For n = 8: 8 ⊕ 9 ⊕ ... ⊕ 14 The optimal value of x is: 14 Constraints 4 ≤ n ≤ 10¹² n is divisible by 4 n ≤ x < 2n x must have the same bit-length as n Output Return the value of x that maximizes: n ⊕ (n + 1) ⊕ ... ⊕ x If multiple values are optimal, return the smallest x."