Minimum Removals to Achieve Target XOR - Solution & Explanation
Problem Statement
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:
- Removing
nums[1] = 2leaves[nums[0], nums[2]] = [1, 3]. - The XOR of
[1, 3]is 2, which equalstarget. - It is not possible to achieve XOR = 2 in less than one removal, therefore the answer is 1.
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 <= 104
Approach Overview
Problem 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 1: Default Approach
Code
Python
Java
C++
Go
TypeScript
Approach 2: Dynamic Programming
We define a 2D array f, where f[i][j] represents the maximum number of elements we can select from the first i elements such that their XOR sum equals j. Initially, f[0][0] = 0 and all other f[0][j] are negative infinity.
For each element nums[i - 1], we can choose not to use it, in which case f[i][j] equals f[i - 1][j]; or we can choose to use it, in which case f[i][j] equals f[i - 1][j \oplus nums[i - 1]] + 1. Thus, the transition equation is:
$
\begin{aligned}
f[i][j] = max(f[i - 1][j], f[i - 1][j \oplus nums[i - 1]] + 1)
\end{aligned}
Finally, if f[n][target] is less than 0, it means the target XOR value cannot be achieved, and we return -1; otherwise, we return n - f[n][target], which is the number of elements that need to be removed.
The time complexity is O(n times 2^m) and the space complexity is O(n times 2^m), where n is the length of the array and m$ is the number of binary bits of the maximum element in the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Default Approach | — |
| Dynamic Programming | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 3877 | Minimum Removals to Achieve Target XOR | Leetcode weekly contest 494 • CodeWithMeGuys • 893 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Minimum Removals to Achieve Target XOR easy or hard?
Minimum Removals to Achieve Target XOR Python/Java solution
How to solve Minimum Removals to Achieve Target XOR in O(n)?
What is the best approach for Minimum Removals to Achieve Target XOR?
Is Minimum Removals to Achieve Target XOR asked at Google/Amazon/Meta?
What data structure is used in Minimum Removals to Achieve Target XOR?
What is the time complexity of Minimum Removals to Achieve Target XOR?
Ready to solve this problem?
Practice Minimum Removals to Achieve Target XOR with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor