LeetCode Problem 3877

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Bit Manipulation

Solution

LeetCode 3877 - Minimum Removals to Achieve Target XOR

Problem Understanding

We are given an array nums and a target value target. We may remove any subset of elements from the array, including removing none of them or even removing all of them.

After performing the removals, the remaining elements form a new array. The bitwise XOR of all remaining elements must equal target. Our goal is to minimize the number of removed elements.

A useful way to restate the problem is:

• We want to keep as many elements as possible.
• The XOR of all kept elements must equal target.
• If we can find the largest subset whose XOR equals target, then the answer is:

$$\text{removals} = n - \text{largest valid subset size}$$

where n is the length of nums.

The constraints are particularly important:

• 1 <= nums.length <= 40
• 0 <= nums[i] <= 10^4
• 0 <= target <= 10^4

A length of 40 is small enough that exponential algorithms may be possible, but not the naive 2^40 brute force. Since:

$$2^{40} \approx 10^{12}$$

enumerating every subset directly is impossible.

However:

$$2^{20} \approx 10^6$$

which is large but manageable. This strongly suggests a meet-in-the-middle approach.

Important edge cases include:

• The entire array already XORs to target, giving answer 0.
• The only way to achieve target is with the empty subset, whose XOR is 0.
• No subset XOR equals target, requiring us to return -1.
• Multiple subsets may achieve the target, and we must choose the one with the maximum size.
• Arrays containing many zeros, since XOR with zero does not change the value but does affect subset size.

Approaches

Brute Force

The most straightforward approach is to enumerate every subset of the array.

For each subset:

1. Compute its XOR.
2. Count how many elements it contains.
3. If the XOR equals target, update the largest valid subset size.

Finally, return:

$$n - \text{largest valid subset size}$$

This approach is correct because every possible subset is examined.

Unfortunately, there are 2^n subsets. With n = 40, that becomes roughly one trillion subsets, which is far beyond practical limits.

Key Insight

The array length of 40 is too large for full subset enumeration, but small enough for a meet-in-the-middle technique.

Split the array into two halves:

• Left half of size at most 20
• Right half of size at most 20

For each half, enumerate all subset possibilities.

For every subset we record:

• Its XOR value
• Its size

Suppose:

• Left subset XOR = x
• Right subset XOR = y

The combined subset XOR is:

$$x \oplus y$$

We need:

$$x \oplus y = target$$

which implies:

$$y = x \oplus target$$

Therefore, after generating all right-half subsets, we can quickly find the best matching right subset for every left subset.

The only thing we care about is maximizing total subset size. For each XOR value in the right half, we store the largest subset size that produces that XOR.

This reduces the search from 2^40 possibilities to roughly:

$$2^{20} + 2^{20}$$

which is feasible.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n · n)	O(1)	Enumerates every subset
Optimal Meet-in-the-Middle	O(n · 2^(n/2))	O(2^(n/2))	Splits array into two halves and combines results

Algorithm Walkthrough

1. Let n be the length of the array and split it into two halves.
2. Enumerate every subset of the left half. For each subset:

• Compute its XOR value.
• Compute its size.
• Store the pair (xor, size).

3. Enumerate every subset of the right half. For each subset:

• Compute its XOR value.
• Compute its size.
• For each XOR value, keep only the maximum subset size that produces it.

4. Initialize best_kept = -1.
5. For every left-half subset:

• Let its XOR be left_xor.
• Let its size be left_size.
• Compute the required right XOR:

$$required = left_xor \oplus target$$

1. Check whether required exists among the right-half XOR values.
2. If it exists, then combining the two subsets produces exactly target.
3. Compute:

$$total_size = left_size + rightBest[required]$$

and update the largest valid subset size.

1. After processing all left subsets:

• If no valid subset was found, return -1.
• Otherwise return:

$$n - best_kept$$

Why it works

Every subset of the original array can be uniquely represented as the union of one subset from the left half and one subset from the right half. The algorithm enumerates all possibilities from both halves. For every left subset, it finds exactly the right subsets that complete the XOR to target. Since we store the maximum right-side size for each XOR value, we always obtain the largest possible total subset size achieving target. Therefore the resulting number of removals is minimal.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def minRemovals(self, nums: List[int], target: int) -> int:
        n = len(nums)

        mid = n // 2
        left = nums[:mid]
        right = nums[mid:]

        left_subsets = []

        for mask in range(1 << len(left)):
            xor_value = 0
            size = 0

            for i in range(len(left)):
                if mask & (1 << i):
                    xor_value ^= left[i]
                    size += 1

            left_subsets.append((xor_value, size))

        best_right = {}

        for mask in range(1 << len(right)):
            xor_value = 0
            size = 0

            for i in range(len(right)):
                if mask & (1 << i):
                    xor_value ^= right[i]
                    size += 1

            if xor_value not in best_right:
                best_right[xor_value] = size
            else:
                best_right[xor_value] = max(best_right[xor_value], size)

        best_kept = -1

        for left_xor, left_size in left_subsets:
            required = left_xor ^ target

            if required in best_right:
                best_kept = max(
                    best_kept,
                    left_size + best_right[required]
                )

        if best_kept == -1:
            return -1

        return n - best_kept

The implementation begins by splitting the array into two halves. Every subset of the left half is enumerated and stored as a (xor, size) pair.

Next, all right-half subsets are generated. Instead of storing every subset separately, we only keep the maximum subset size for each XOR value. This compression is important because multiple subsets may generate the same XOR.

The final phase iterates through all left subsets. For each one, we compute the XOR value needed from the right side. If such a value exists, we combine the subset sizes and update the largest valid subset found so far.

Once all combinations have been examined, the answer is simply the number of removed elements, which equals the total length minus the largest valid kept subset size.

Go Solution

func minRemovals(nums []int, target int) int {
	n := len(nums)

	mid := n / 2
	left := nums[:mid]
	right := nums[mid:]

	type Pair struct {
		xorVal int
		size   int
	}

	leftSubsets := make([]Pair, 0, 1<<len(left))

	for mask := 0; mask < (1 << len(left)); mask++ {
		xorVal := 0
		size := 0

		for i := 0; i < len(left); i++ {
			if (mask & (1 << i)) != 0 {
				xorVal ^= left[i]
				size++
			}
		}

		leftSubsets = append(leftSubsets, Pair{xorVal, size})
	}

	bestRight := make(map[int]int)

	for mask := 0; mask < (1 << len(right)); mask++ {
		xorVal := 0
		size := 0

		for i := 0; i < len(right); i++ {
			if (mask & (1 << i)) != 0 {
				xorVal ^= right[i]
				size++
			}
		}

		if oldSize, ok := bestRight[xorVal]; !ok || size > oldSize {
			bestRight[xorVal] = size
		}
	}

	bestKept := -1

	for _, p := range leftSubsets {
		required := p.xorVal ^ target

		if rightSize, ok := bestRight[required]; ok {
			totalSize := p.size + rightSize
			if totalSize > bestKept {
				bestKept = totalSize
			}
		}
	}

	if bestKept == -1 {
		return -1
	}

	return n - bestKept
}

The Go implementation follows exactly the same meet-in-the-middle strategy. A small struct is used to store (xor, size) pairs for left subsets. A map records the maximum subset size for every right-half XOR value. Since all values fit comfortably within Go's int type, there are no overflow concerns.

Worked Examples

Example 1

Input

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

Split:

left  = [1]
right = [2,3]

Left subsets:

Subset	XOR	Size
{}	0	0
{1}	1	1

Right subsets:

Subset	XOR	Size
{}	0	0
{2}	2	1
{3}	3	1
{2,3}	1	2

Best right map:

XOR	Max Size
0	0
1	2
2	1
3	1

Combine:

Left XOR	Left Size	Required XOR	Right Size	Total Size
0	0	2	1	1
1	1	3	1	2

Largest kept subset size:

2

Answer:

3 - 2 = 1

Example 2

Input

nums = [2,4]
target = 1

Split:

left = [2]
right = [4]

Left subsets:

XOR	Size
0	0
2	1

Right subsets:

XOR	Size
0	0
4	1

Required XOR values:

Left XOR	Required
0	1
2	3

Neither 1 nor 3 exists in the right map.

No valid subset exists.

Answer:

-1

Example 3

Input

nums = [7]
target = 7

Split:

left = []
right = [7]

Right subsets:

XOR	Size
0	0
7	1

For the empty left subset:

required = 0 ^ 7 = 7

Matching right subset size:

1

Largest kept size:

1

Answer:

1 - 1 = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n · 2^(n/2))	Enumerating all subsets of both halves
Space	O(2^(n/2))	Stores subset information and XOR mappings

The array is divided into two halves of size at most 20. Each half generates at most 2^20 subsets. Computing each subset's XOR and size requires iterating through up to 20 positions, giving a total complexity of O(n · 2^(n/2)). This is efficient enough for n = 40.

Test Cases

sol = Solution()

assert sol.minRemovals([1, 2, 3], 2) == 1      # provided example 1
assert sol.minRemovals([2, 4], 1) == -1        # provided example 2
assert sol.minRemovals([7], 7) == 0            # provided example 3

assert sol.minRemovals([5], 0) == 1            # must remove only element
assert sol.minRemovals([0], 0) == 0            # keep single zero

assert sol.minRemovals([1, 1], 0) == 0         # entire array XORs to 0
assert sol.minRemovals([1, 2], 3) == 0         # already target

assert sol.minRemovals([1, 2], 0) == 2         # only empty subset works

assert sol.minRemovals([0, 0, 0], 0) == 0      # all zeros

assert sol.minRemovals([4, 4, 4], 4) == 0      # keep all elements

assert sol.minRemovals([1, 2, 4, 8], 15) == 0  # XOR of all elements

assert sol.minRemovals([1, 2, 4, 8], 7) == 1   # keep subset {1,2,4}

assert sol.minRemovals([3, 5, 6, 7], 1) == 1   # nontrivial combination

assert sol.minRemovals([10000] * 40, 0) == 0   # maximum length stress case

Test Summary

Test	Why
[1,2,3], target=2	Provided example
[2,4], target=1	Impossible target
[7], target=7	Single element already valid
[5], target=0	Must remove everything
[0], target=0	Single zero
[1,1], target=0	XOR cancellation
[1,2], target=3	Entire array already works
[1,2], target=0	Empty subset required
[0,0,0], target=0	Many zeros
[4,4,4], target=4	Duplicate values
[1,2,4,8], target=15	All elements needed
[1,2,4,8], target=7	Proper subset optimal
[3,5,6,7], target=1	Mixed XOR combinations
[10000]*40, target=0	Maximum-size stress test

Edge Cases

The Empty Subset Is the Only Valid Solution

Since the XOR of an empty array is defined as 0, it is possible that the only way to achieve the target is by removing every element. A common bug is forgetting to consider the empty subset. This implementation explicitly enumerates subset mask 0 in both halves, guaranteeing that the empty subset is included.

Multiple Subsets Produce the Same XOR

Different subsets can generate identical XOR values. If we stored only one arbitrary subset for each XOR, we might miss a larger valid subset and return too many removals. The algorithm stores the maximum subset size for every right-half XOR value, ensuring the largest possible kept subset is always used.

Arrays Containing Many Zeros

Zero values do not affect XOR but do increase subset size. For example, if the target XOR is already achieved, keeping additional zeros is always beneficial because it reduces removals. By maximizing subset size for every XOR value, the algorithm automatically prefers solutions that retain such extra elements.

No Valid Subset Exists

Some targets cannot be produced by any subset XOR. In that situation, the combination phase never finds a matching pair of XOR values and best_kept remains -1. The implementation detects this condition and correctly returns -1.

Maximum Constraint Size

With 40 elements, a full subset search would require approximately 2^40 checks, which is infeasible. The meet-in-the-middle technique reduces the work to roughly 2 * 2^20 subset generations, allowing the solution to comfortably fit within competitive programming limits while still examining every possible subset implicitly.