Skip to content

3755. Find Maximum Balanced XOR Subarray Length

Description

Given an integer array nums, return the length of the longest subarray that has a bitwise XOR of zero and contains an equal number of even and odd numbers. If no such subarray exists, return 0.

 

Example 1:

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

Output: 4

Explanation:

The subarray [1, 3, 2, 0] has bitwise XOR 1 XOR 3 XOR 2 XOR 0 = 0 and contains 2 even and 2 odd numbers.

Example 2:

Input: nums = [3,2,8,5,4,14,9,15]

Output: 8

Explanation:

The whole array has bitwise XOR 0 and contains 4 even and 4 odd numbers.

Example 3:

Input: nums = [0]

Output: 0

Explanation:

No non-empty subarray satisfies both conditions.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

Solutions

Solution 1: Prefix Sum + Hash Table

We use a hash table to record the first occurrence position of each state \((a, b)\), where \(a\) represents the prefix XOR sum, and \(b\) represents the prefix even count minus the prefix odd count. When we encounter the same state \((a, b)\) while traversing the array, it means that the subarray from the last occurrence of this state to the current position satisfies both bitwise XOR equals 0 and equal counts of even and odd numbers. We can then update the answer by taking the maximum length. Otherwise, we store this state and the current position in the hash table.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxBalancedSubarray(self, nums: List[int]) -> int:
        d = {(0, 0): -1}
        a = b = 0
        ans = 0
        for i, x in enumerate(nums):
            a ^= x
            b += 1 if x % 2 == 0 else -1
            if (a, b) in d:
                ans = max(ans, i - d[(a, b)])
            else:
                d[(a, b)] = i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxBalancedSubarray(int[] nums) {
        Map<Long, Integer> d = new HashMap<>();
        int ans = 0;
        int a = 0, b = nums.length;
        d.put((long) b, -1);
        for (int i = 0; i < nums.length; ++i) {
            a ^= nums[i];
            b += nums[i] % 2 == 0 ? 1 : -1;
            long key = (1L * a << 32) | b;
            if (d.containsKey(key)) {
                ans = Math.max(ans, i - d.get(key));
            } else {
                d.put(key, i);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxBalancedSubarray(vector<int>& nums) {
        unordered_map<long long, int> d;
        int ans = 0;
        int a = 0, b = nums.size();
        d[(long long) b] = -1;
        for (int i = 0; i < nums.size(); ++i) {
            a ^= nums[i];
            b += nums[i] % 2 == 0 ? 1 : -1;
            long long key = (1LL * a << 32) | b;
            if (d.contains(key)) {
                ans = max(ans, i - d[key]);
            } else {
                d[key] = i;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func maxBalancedSubarray(nums []int) (ans int) {
    d := map[int64]int{}
    a := 0
    b := len(nums)
    d[int64(b)] = -1
    for i, x := range nums {
        a ^= x
        if x%2 == 0 {
            b++
        } else {
            b--
        }
        key := int64(a)<<32 | int64(b)
        if j, ok := d[key]; ok {
            ans = max(ans, i-j)
        } else {
            d[key] = i
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function maxBalancedSubarray(nums: number[]): number {
    const d = new Map<bigint, number>();
    let ans = 0;
    let a = 0;
    let b = nums.length;
    d.set(BigInt(b), -1);
    for (let i = 0; i < nums.length; ++i) {
        a ^= nums[i];
        b += nums[i] % 2 === 0 ? 1 : -1;
        const key = (BigInt(a) << 32n) | BigInt(b);
        if (d.has(key)) {
            ans = Math.max(ans, i - d.get(key)!);
        } else {
            d.set(key, i);
        }
    }
    return ans;
}

Comments