3877. Minimum Removals to Achieve Target XOR

MediumBit ManipulationArrayDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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.

In other words, you want to keep as many elements as possible from nums such that the XOR of all kept elements is exactly equal to target. Since removing fewer elements means keeping more elements, the goal is to maximize the number of elements retained while ensuring their XOR equals target. The answer is then the total number of elements minus the maximum number of elements we can keep. If no subset of nums can produce an XOR equal to target, the task is impossible and you should return -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

The problem asks to minimize removals by choosing which elements to keep to reach a target XOR, solved with a DP over XOR states.

Open in Flowchart

Intuition

The key observation is that "minimizing the number of removals" is equivalent to "maximizing the number of elements we keep." If the array has n elements and we can keep at most k of them while their XOR equals target, then the minimum number of removals is simply n - k.

So the problem transforms into: select the largest possible subset of nums whose XOR sum equals target.

How do we decide which elements to keep? For each element, we face a simple binary choice: either include it in our kept subset or leave it out. The tricky part is that the XOR value depends on the exact combination of elements we choose, so we cannot greedily decide one element at a time without tracking the resulting XOR.

This naturally leads us to track two things as we process elements one by one:

How many elements we have considered so far.
What XOR value the currently selected elements produce.

Once we fix these two pieces of information, the answer for that state (the maximum number of elements selected to reach that XOR) is well-defined and can be reused. This "reusable subproblem" structure is exactly what dynamic programming handles well.

Let f[i][j] represent the maximum number of elements we can select from the first i elements so that their XOR equals j. When we look at the i-th element x, we have two options:

Skip it: the state stays the same as f[i - 1][j].
Take it: before adding x, the previous XOR must have been j ^ x (because XOR-ing j ^ x with x gives back j). In this case the count increases by 1, giving f[i - 1][j ^ x] + 1.

We pick whichever option keeps more elements. Starting from f[0][0] = 0 (an empty selection has XOR 0 and zero elements), all other states begin as negative infinity to mark them unreachable.

One more detail: the XOR of any subset can never exceed the largest bit-length seen among the numbers. If target requires a higher bit than what the elements can ever produce, the target is unreachable and we immediately return -1. After filling the table, if f[n][target] is still negative, no valid subset exists; otherwise, the answer is n - f[n][target].

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: 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 (meaning those XOR values are unreachable with zero selected elements).

Step 1: Determine the bound of XOR values.

Since XOR never sets a bit higher than the highest bit appearing in any of the numbers, we compute m = max(nums).bit_length(), which tells us the number of bits needed to represent the largest element. The possible XOR values then range over 0 to (1 << m) - 1. If target is too large to ever be produced, that is (1 << m) <= target, we immediately return -1.

Step 2: Initialize the DP table.

We create the table f with n + 1 rows and 1 << m columns, filled with -inf, and set f[0][0] = 0 to mark the base case: an empty selection has XOR 0 and uses zero elements.

Step 3: Fill the table with the transition.

For each element x = nums[i - 1] (iterating with i from 1 to n) and for each possible XOR value j in the range [0, 1 << m), we consider two choices:

Skip x: the state is inherited directly from the previous row, f[i - 1][j].
Take x: the previous XOR must have been j ^ x, and selecting x adds one element, giving f[i - 1][j ^ x] + 1.

We keep the larger of the two:

f[i][j] = \max(f[i - 1][j], f[i - 1][j \oplus x] + 1)

Step 4: Extract the answer.

After filling the table, we look at f[n][target]. If it is still negative, no subset can reach target, so we return -1. Otherwise, f[n][target] is the maximum number of elements we can keep, and the minimum number of removals is n - f[n][target].

Complexity Analysis:

Time complexity: O(n × 2^m), where n is the length of nums and m is the bit-length of the maximum element. We iterate over every element and every possible XOR value once.
Space complexity: O(n × 2^m) for the 2D table. This can be optimized to O(2^m) by noticing that each row only depends on the previous row, allowing us to use a single rolling array.

Example Walkthrough

Let's trace through a small example to see how the dynamic programming approach works.

Input: nums = [1, 3, 2], target = 3

We want to keep as many elements as possible such that their XOR equals 3.

Step 1: Determine the bound of XOR values.

The maximum element is 3, whose binary representation is 11, so m = 3.bit_length() = 2. The possible XOR values range over [0, 1 << 2) = [0, 4), that is {0, 1, 2, 3}.

Since (1 << m) = 4 > target = 3, the target is potentially reachable, so we continue.

Step 2: Initialize the DP table.

We build f with n + 1 = 4 rows and 1 << m = 4 columns, all set to -inf, except f[0][0] = 0.

i \ j	0	1	2	3
0	0	-inf	-inf	-inf
1
2
3

Step 3: Fill the table.

Row i = 1 (element x = nums[0] = 1):

For each j, we compute max(f[0][j], f[0][j ^ 1] + 1):

j = 0: max(f[0][0], f[0][1] + 1) = max(0, -inf) = 0
j = 1: max(f[0][1], f[0][0] + 1) = max(-inf, 0 + 1) = 1
j = 2: max(f[0][2], f[0][3] + 1) = max(-inf, -inf) = -inf
j = 3: max(f[0][3], f[0][2] + 1) = max(-inf, -inf) = -inf

Row i = 2 (element x = nums[1] = 3):

For each j, we compute max(f[1][j], f[1][j ^ 3] + 1):

j = 0: max(f[1][0], f[1][3] + 1) = max(0, -inf) = 0
j = 1: max(f[1][1], f[1][2] + 1) = max(1, -inf) = 1
j = 2: max(f[1][2], f[1][1] + 1) = max(-inf, 1 + 1) = 2
j = 3: max(f[1][3], f[1][0] + 1) = max(-inf, 0 + 1) = 1

Here f[2][2] = 2 means we kept both 1 and 3 (since 1 ^ 3 = 2).

Row i = 3 (element x = nums[2] = 2):

For each j, we compute max(f[2][j], f[2][j ^ 2] + 1):

j = 0: max(f[2][0], f[2][2] + 1) = max(0, 2 + 1) = 3
j = 1: max(f[2][1], f[2][3] + 1) = max(1, 1 + 1) = 2
j = 2: max(f[2][2], f[2][0] + 1) = max(2, 0 + 1) = 2
j = 3: max(f[2][3], f[2][1] + 1) = max(1, 1 + 1) = 2

Completed table:

i \ j	0	1	2	3
0	0	-inf	-inf	-inf
1	0	1	-inf	-inf
2	0	1	2	1
3	3	2	2	2

Step 4: Extract the answer.

We look at f[n][target] = f[3][3] = 2. This is non-negative, so a valid subset exists. The maximum number of elements we can keep is 2, and the minimum number of removals is:

n - f[n][target] = 3 - 2 = 1

Verification: Keeping 1 and 2 gives 1 ^ 2 = 3 = target, using just 2 elements and removing 1 element. We could also keep 3 alone (3 = target), which also keeps only 1 element. The DP correctly found that the best we can do is keep 2 elements, so the answer is 1. ✓

Solution Implementation

1from typing import List
2from math import inf
3
4
5class Solution:
6    def minRemovals(self, nums: List[int], target: int) -> int:
7        # Determine the number of bits needed to represent the largest value.
8        # This bounds the range of possible XOR results.
9        num_bits = max(nums).bit_length()
10
11        # If target requires more bits than any achievable XOR value,
12        # it can never be formed, so removal is impossible.
13        if (1 << num_bits) <= target:
14            return -1
15
16        n = len(nums)
17
18        # dp[i][xor_val] = maximum number of elements kept among the first i
19        # elements such that their XOR equals xor_val.
20        # Initialize with -inf to mark unreachable states.
21        dp = [[-inf] * (1 << num_bits) for _ in range(n + 1)]
22
23        # Base case: keeping zero elements gives an XOR of 0.
24        dp[0][0] = 0
25
26        # Process each element in turn (1-indexed for the dp table).
27        for i, x in enumerate(nums, 1):
28            for xor_val in range(1 << num_bits):
29                # Option 1: skip the current element x.
30                # Option 2: keep x, which means the previous XOR must have
31                #           been (xor_val ^ x) so that adding x yields xor_val.
32                dp[i][xor_val] = max(
33                    dp[i - 1][xor_val],
34                    dp[i - 1][xor_val ^ x] + 1,
35                )
36
37        # If no valid subset achieves the target XOR, it's impossible.
38        if dp[n][target] < 0:
39            return -1
40
41        # The minimum removals equals total elements minus the maximum kept.
42        return n - dp[n][target]
43

1class Solution {
2    public int minRemovals(int[] nums, int target) {
3        // Find the maximum value to determine the number of relevant bits
4        int maxValue = 0;
5        for (int x : nums) {
6            maxValue = Math.max(maxValue, x);
7        }
8
9        // m = number of bits needed to represent maxValue
10        int bitCount = 32 - Integer.numberOfLeadingZeros(maxValue);
11
12        // If target requires more bits than any XOR combination can produce,
13        // it's impossible to reach the target XOR value
14        if ((1 << bitCount) <= target) {
15            return -1;
16        }
17
18        int n = nums.length;
19        int maskSize = 1 << bitCount;
20
21        // dp[i][j] = maximum count of selected elements from the first i numbers
22        //            whose XOR equals j; MIN_VALUE means unreachable state
23        int[][] dp = new int[n + 1][maskSize];
24        for (int i = 0; i <= n; i++) {
25            Arrays.fill(dp[i], Integer.MIN_VALUE);
26        }
27
28        // Base case: selecting nothing yields an XOR of 0 with count 0
29        dp[0][0] = 0;
30
31        // Process each number, deciding to either skip it or include it
32        for (int i = 1; i <= n; i++) {
33            int x = nums[i - 1];
34            for (int j = 0; j < maskSize; j++) {
35                // Option 1: skip the current number -> dp[i - 1][j]
36                // Option 2: include the current number -> dp[i - 1][j ^ x] + 1
37                //           (previous XOR was j ^ x, adding x makes it j)
38                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j ^ x] + 1);
39            }
40        }
41
42        // If the target XOR state is unreachable, return -1
43        if (dp[n][target] < 0) {
44            return -1;
45        }
46
47        // Removals = total elements - maximum elements kept to reach target XOR
48        return n - dp[n][target];
49    }
50}
51

1class Solution {
2public:
3    int minRemovals(vector<int>& nums, int target) {
4        // Find the maximum value in nums to determine the number of bits needed
5        int maxVal = ranges::max(nums);
6
7        // Compute the smallest bit-width that can represent maxVal
8        // bitWidth is the number of bits such that (1 << bitWidth) > maxVal
9        int bitWidth = 0;
10        while ((1 << bitWidth) <= maxVal) {
11            ++bitWidth;
12        }
13
14        // If target requires more bits than our representable range,
15        // it can never be formed, so return -1
16        if ((1 << bitWidth) <= target) {
17            return -1;
18        }
19
20        int n = nums.size();
21        int maskSize = 1 << bitWidth; // total number of possible XOR states
22
23        // dp[i][j] = the maximum number of elements we can KEEP
24        // using the first i elements such that their XOR equals j.
25        // Initialize with INT_MIN to denote unreachable states.
26        vector<vector<int>> dp(n + 1, vector<int>(maskSize, INT_MIN));
27
28        // Base case: using 0 elements, XOR is 0, and we kept 0 elements
29        dp[0][0] = 0;
30
31        // Process each element one by one
32        for (int i = 1; i <= n; ++i) {
33            int x = nums[i - 1]; // current element value
34            for (int j = 0; j < maskSize; ++j) {
35                // Option 1: skip nums[i-1], state j is inherited from previous row
36                // Option 2: keep nums[i-1], then the previous XOR must have been (j ^ x),
37                //           and we gain one more kept element
38                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j ^ x] + 1);
39            }
40        }
41
42        // If the target XOR state is unreachable, return -1
43        if (dp[n][target] < 0) {
44            return -1;
45        }
46
47        // Minimum removals = total elements - maximum kept elements
48        return n - dp[n][target];
49    }
50};
51

1/**
2 * Returns the minimum number of removals from `nums` so that the XOR
3 * of the remaining elements equals `target`. Returns -1 if impossible.
4 *
5 * @param nums   - input array of non-negative integers
6 * @param target - desired XOR value of the kept subset
7 * @returns minimum removals, or -1 if no valid subset exists
8 */
9function minRemovals(nums: number[], target: number): number {
10    // Find the maximum value to determine how many bits we need.
11    const maxValue: number = Math.max(...nums);
12
13    // Compute the bit width `bitWidth` such that (1 << bitWidth) covers all values.
14    let bitWidth: number = 0;
15    while (1 << bitWidth <= maxValue) {
16        bitWidth++;
17    }
18
19    // If `target` cannot be represented within the value range, it's impossible.
20    if (1 << bitWidth <= target) {
21        return -1;
22    }
23
24    const n: number = nums.length;
25    const maskCount: number = 1 << bitWidth;
26
27    // dp[i][j] = maximum count of elements chosen from the first `i` numbers
28    //            whose XOR equals `j`. -Infinity means unreachable.
29    const dp: number[][] = Array.from({ length: n + 1 }, () =>
30        new Array<number>(maskCount).fill(-Infinity),
31    );
32
33    // Base case: choosing nothing yields XOR 0 with 0 elements.
34    dp[0][0] = 0;
35
36    // Process each number one by one.
37    for (let i = 1; i <= n; i++) {
38        const current: number = nums[i - 1];
39        for (let xorValue = 0; xorValue < maskCount; xorValue++) {
40            // Either skip `current` (keep previous state),
41            // or include it (XOR removes/applies its bits and adds 1 to the count).
42            dp[i][xorValue] = Math.max(
43                dp[i - 1][xorValue],
44                dp[i - 1][xorValue ^ current] + 1,
45            );
46        }
47    }
48
49    // If the target XOR is unreachable, return -1.
50    if (dp[n][target] < 0) {
51        return -1;
52    }
53
54    // Removals = total elements minus the maximum number we can keep.
55    return n - dp[n][target];
56}
57

Time and Space Complexity

Time complexity: O(n × 2^m), where n is the length of the array nums, and m is the number of binary bits of the maximum element in the array. The code uses two nested loops: the outer loop iterates over the n elements of nums, and the inner loop iterates over all 1 << m (i.e., 2^m) possible XOR states. Each state transition f[i][j] = max(f[i - 1][j], f[i - 1][j ^ x] + 1) takes O(1) time, so the total time complexity is O(n × 2^m).
Space complexity: O(n × 2^m). The two-dimensional array f has dimensions (n + 1) × (1 << m), requiring O(n × 2^m) space to store all the intermediate states.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Computing the bit-length bound from `nums` only, ignoring `target`

The most subtle bug in this solution lies in Step 1, where the XOR universe size is derived solely from max(nums):

num_bits = max(nums).bit_length()
if (1 << num_bits) <= target:
    return -1

The intent behind the early return is correct: a XOR of any subset of nums can never set a bit higher than the highest bit present in any element, so if target has a bit beyond that range, it is unachievable. However, two issues hide here:

Issue A — The DP table is too small when target has a high bit.

If target is not greater than (1 << num_bits) but is still reachable, everything works. But consider what happens when target shares the same top bit as max(nums). The table has 1 << num_bits columns, indexing 0 .. (1 << num_bits) - 1. As long as target < (1 << num_bits), indexing dp[n][target] is safe. The guard (1 << num_bits) <= target correctly catches the out-of-range case. So far so good — but the expression xor_val ^ x inside the loop is always < (1 << num_bits) because both operands are, so no out-of-bounds access occurs there either.

The real risk appears when you try to size the table by max(nums) alone while later code assumes target indexes into it. The current guard saves us, but it is fragile. A safer formulation makes the bound explicit over both sources:

num_bits = max(max(nums), target).bit_length()

This way the table is guaranteed large enough to index target, and the only "impossible" case is when target has a strictly higher bit than every element — which you then detect separately.

Issue B — max(nums) crashes on an empty array.

If nums == [], max(nums) raises a ValueError. The empty-array case should be handled up front: the XOR of an empty array is 0, so the answer is 0 if target == 0, else -1.

if not nums:
    return 0 if target == 0 else -1

Pitfall 2: Confusing "removals" with "kept" in the final answer

A frequent mistake is returning dp[n][target] directly. Remember dp[n][target] is the maximum number of elements kept, while the problem asks for minimum removals:

return n - dp[n][target]   # correct
# return dp[n][target]     # WRONG — this is the count kept, not removed

Pitfall 3: Forgetting that the empty subset is valid for `target == 0`

Because dp[0][0] = 0 and the "skip" transition propagates it forward, the algorithm naturally allows keeping zero elements when target == 0. A buggy initialization (e.g., starting all states at -inf including dp[0][0]) would incorrectly report -1 for target == 0 even though removing everything is always a valid answer.

Pitfall 4: Memory blowup from the 2D table

The 2D table costs O(n × 2^m) space, which can be large. Since each row depends only on the previous one, collapse it into a rolling 1D array. Note the subtlety: when updating in place you must read from the previous state, so iterate using a fresh copy per element:

from typing import List
from math import inf


class Solution:
    def minRemovals(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0 if target == 0 else -1

        num_bits = max(max(nums), target).bit_length()
        size = 1 << num_bits

        # If target has a bit beyond what any element can contribute, impossible.
        if target >= size:
            return -1

        # dp[xor_val] = max elements kept so far achieving this XOR.
        dp = [-inf] * size
        dp[0] = 0

        for x in nums:
            # Copy so each element's transition reads pre-update values.
            prev = dp[:]
            for xor_val in range(size):
                dp[xor_val] = max(prev[xor_val], prev[xor_val ^ x] + 1)

        return -1 if dp[target] < 0 else len(nums) - dp[target]

This preserves correctness while reducing space to O(2^m).

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: