Is Minimum Removals to Achieve Target XOR easy or hard?

The problem is typically rated Medium because the brute-force idea is simple but recognizing the XOR transformation and applying dynamic programming over XOR states requires deeper insight.

Minimum Removals to Achieve Target XOR Python/Java solution

Implement the DP using a dictionary or HashMap where dp[x] tracks the minimum removals for XOR x. For each number, update transitions to x ^ num with cost +1 while preserving existing states. The same logic translates directly across Python, Java, C++, Go, and TypeScript.

How to solve Minimum Removals to Achieve Target XOR in O(n)?

A strict O(n) algorithm is generally not possible because the solution must track multiple XOR states. The closest practical optimization uses a hash map DP that processes each element once while updating reachable XOR values, giving O(n * U) complexity with small state growth.

What is the best approach for Minimum Removals to Achieve Target XOR?

The most effective approach uses XOR transformation plus hash map dynamic programming. Compute the XOR of the entire array S, then find the minimum-size subset whose XOR equals S ^ target. A DP map tracks the minimum removals needed for each XOR state. This runs in O(n * U) time where U is the number of reachable XOR states.

Is Minimum Removals to Achieve Target XOR asked at Google/Amazon/Meta?

XOR-based subset and dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving subset XOR, prefix XOR, or minimizing operations are common because they test bit manipulation and DP reasoning.

What data structure is used in Minimum Removals to Achieve Target XOR?

A hash map is used to store dynamic programming states where the key represents a reachable XOR value and the value stores the minimum number of removals needed to achieve it. The solution also relies on bit manipulation properties of the XOR operation.

What is the time complexity of Minimum Removals to Achieve Target XOR?

The optimized solution runs in O(n * U) time and O(U) space, where U is the number of distinct XOR values generated during DP transitions. In the worst case U can approach 2^k for k-bit numbers, but in practice it remains much smaller than 2^n.

Description Hints 1 Solution Video 14:06

3877. Minimum Removals to Achieve Target XOR

Medium41.2% acceptance

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] = 2 leaves [nums[0], nums[2]] = [1, 3].
The XOR of [1, 3] is 2, which equals target.
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 <= 40
0 <= nums[i] <= 10⁴
0 <= target <= 10⁴

Topics

Hints open one at a time

Hint 1

Use meet in the middle or dynamic programming

14:06

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minRemovals(self, nums: List[int], target: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3]
2

Input

[2,4]
1

Input

[7]
7

Your code is saved on this device.Solution