Watch 4 video solutions for Minimum Removals to Achieve Target XOR, a medium level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by CodeWithMeGuys has 775 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums and an integer target.
You may remove any number of elements from nums (possibly zero).
Return the minimum number of removals required so that the bitwise XOR of the remaining elements equals target. If it is impossible to achieve target, return -1.
The bitwise XOR of an empty array is 0.
Example 1:
Input: nums = [1,2,3], target = 2
Output: 1
Explanation:
nums[1] = 2 leaves [nums[0], nums[2]] = [1, 3].[1, 3] is 2, which equals target.Example 2:
Input: nums = [2,4], target = 1
Output: -1
Explanation:
It is impossible to remove elements to achieve target. Thus, the answer is -1.
Example 3:
Input: nums = [7], target = 7
Output: 0
Explanation:
The XOR of all elements is nums[0] = 7, which equals target. Thus, no removal is needed.
Constraints:
1 <= nums.length <= 400 <= nums[i] <= 1040 <= target <= 104Problem Overview: Given an array of integers and a target value, remove the minimum number of elements so the XOR of the remaining elements equals the target. The task reduces to deciding which elements to remove while preserving the desired XOR.
Approach 1: Brute Force Subset Enumeration (O(2^n) time, O(1) space)
Try every subset of elements to remove. For each subset, compute the XOR of the remaining elements and check whether it equals the target. Track the minimum removal count across all valid subsets. This works because every element has two choices: keep or remove. The method is straightforward but infeasible once n grows beyond ~20 since it requires evaluating 2^n possibilities.
Approach 2: XOR Transformation + Hash Map Dynamic Programming (O(n * U) time, O(U) space)
Let S be the XOR of the entire array. If you remove a subset with XOR R, the remaining XOR becomes S ^ R. To achieve the target, the removed subset must satisfy R = S ^ target. The problem becomes finding a subset whose XOR equals this value while minimizing the number of removed elements.
Use dynamic programming with a hash map: dp[x] stores the minimum removals needed to achieve XOR x using processed elements. Start with dp[0] = 0. For each number, update states by either skipping it (keep element) or including it in the removed subset (XOR transition x ^ num with cost +1). A hash map keeps only reachable XOR states. After processing all elements, the answer is dp[S ^ target] if it exists.
This technique relies on properties of bit manipulation and XOR symmetry. The number of distinct XOR states U is typically small compared with 2^n, making the approach efficient in practice.
Approach 3: DP with State Compression (O(n * U) time, O(U) space)
The same idea can be implemented with rolling maps to avoid overwriting states during iteration. For each number, clone the current map and update new XOR states derived from removing that number. This pattern mirrors classic dynamic programming over subsets but stores only reachable XOR values rather than full bitmasks.
Recommended for interviews: The XOR transformation plus hash map DP is the expected solution. Explaining the identity S ^ R = target shows understanding of XOR algebra. Brute force demonstrates the baseline reasoning, but the DP approach proves you can optimize exponential subset search using state compression.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n) | O(1) | Small arrays (n ≤ 20) or for conceptual understanding |
| Hash Map XOR Dynamic Programming | O(n * U) | O(U) | General case; efficiently tracks reachable XOR states |
| Rolling Map State Compression | O(n * U) | O(U) | Cleaner DP implementation that avoids overwriting states |