3877. Minimum Removals to Achieve Target XOR

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.

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⁴

Solutions

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.

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.

class Solution {
    public int minRemovals(int[] nums, int target) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        int m = 32 - Integer.numberOfLeadingZeros(mx);
        if ((1 << m) <= target) {
            return -1;
        }

        int n = nums.length;
        int[][] f = new int[n + 1][1 << m];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(f[i], Integer.MIN_VALUE);
        }
        f[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int j = 0; j < (1 << m); j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i - 1][j ^ x] + 1);
            }
        }

        if (f[n][target] < 0) {
            return -1;
        }
        return n - f[n][target];
    }
}

class Solution {
public:
    int minRemovals(vector<int>& nums, int target) {
        int mx = ranges::max(nums);
        int m = 0;
        while ((1 << m) <= mx) {
            ++m;
        }
        if ((1 << m) <= target) {
            return -1;
        }

        int n = nums.size();
        vector<vector<int>> f(n + 1, vector<int>(1 << m, INT_MIN));
        f[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int j = 0; j < (1 << m); j++) {
                f[i][j] = max(f[i - 1][j], f[i - 1][j ^ x] + 1);
            }
        }

        if (f[n][target] < 0) {
            return -1;
        }
        return n - f[n][target];
    }
};

class Solution:
    def minRemovals(self, nums: List[int], target: int) -> int:
        m = max(nums).bit_length()
        if (1 << m) <= target:
            return -1
        n = len(nums)
        f = [[-inf] * (1 << m) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(1 << m):
                f[i][j] = max(f[i - 1][j], f[i - 1][j ^ x] + 1)
        if f[n][target] < 0:
            return -1
        return n - f[n][target]

func minRemovals(nums []int, target int) int {
	m := bits.Len(uint(slices.Max(nums)))
	if (1 << m) <= target {
		return -1
	}

	n := len(nums)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, 1<<m)
		for j := range f[i] {
			f[i][j] = math.MinInt
		}
	}
	f[0][0] = 0

	for i := 1; i <= n; i++ {
		x := nums[i-1]
		for j := 0; j < (1 << m); j++ {
			f[i][j] = max(f[i-1][j], f[i-1][j^x]+1)
		}
	}

	if f[n][target] < 0 {
		return -1
	}
	return n - f[n][target]
}

function minRemovals(nums: number[], target: number): number {
    let mx = Math.max(...nums);

    let m = 0;
    while (1 << m <= mx) {
        m++;
    }
    if (1 << m <= target) {
        return -1;
    }

    const n = nums.length;
    const f = Array.from({ length: n + 1 }, () => Array(1 << m).fill(-Infinity));

    f[0][0] = 0;

    for (let i = 1; i <= n; i++) {
        const x = nums[i - 1];
        for (let j = 0; j < 1 << m; j++) {
            f[i][j] = Math.max(f[i - 1][j], f[i - 1][j ^ x] + 1);
        }
    }

    if (f[n][target] < 0) {
        return -1;
    }
    return n - f[n][target];
}

3877 - Minimum Removals to Achieve Target XOR

3877. Minimum Removals to Achieve Target XOR

Description

Solutions

Solution 1: Dynamic Programming

All Problems

All Solutions

Welcome to Subscribe On Youtube

3877. Minimum Removals to Achieve Target XOR

Description

Solutions

Solution 1: Dynamic Programming

All Problems

All Solutions