1829. Maximum XOR for Each Query
Approach
Build XOR prefix; for each query XOR prefix with (2^maximumBit - 1) to flip all bits.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
A prefix sum array pre-computes cumulative values so any range query is answered in O(1). The classic sum of range [l, r] = prefix[r+1] - prefix[l]. 2D prefix sums extend this to matrix sub-rectangle queries. Combine with a hash map for "subarray sum equals k" problems.
// Approach: Build XOR prefix; for each query XOR prefix with (2^maximumBit - 1) to flip all bits.
// Time: O(n) Space: O(n)
public class Solution
{
public int[] GetMaximumXor(int[] nums, int maximumBit)
{
int n = nums.Length;
int mx = (1 << maximumBit) - 1;
int[] ans = new int[n];
int xors = 0;
for (int i = 0; i < n; ++i)
{
xors ^= nums[i];
ans[n - 1 - i] = xors ^ mx;
}
return ans;
}
}