Frontend School

Max Subarray XOR Sum with Bitwise Constraints

DSA
hard

Max Subarray XOR Sum with Bitwise Constraints

Hard
Bit Manipulation
Arrays
Trie
Prefix Sum

Overview

In many real-world applications, especially in financial systems like Paytm, optimizing data processing based on specific bitwise patterns is crucial. For instance, managing feature flags, transaction states, or security permissions often involves bitmasks. This problem challenges you to find a subarray whose bitwise XOR sum adheres to certain target and forbidden bit patterns, while simultaneously maximizing this sum. This tests your ability to design efficient algorithms for complex bitwise constraints over dynamic ranges.

What you need to do / Task

Given an array of non-negative integers nums, and two integer masks targetMask and forbiddenMask, you need to find a contiguous subarray nums[L...R] (where 0 <= L <= R < nums.length) such that its bitwise XOR sum S = nums[L] ^ nums[L+1] ^ ... ^ nums[R] satisfies the following two conditions:

  1. (S & targetMask) == targetMask: All bits set in targetMask must also be set in S.
  2. (S & forbiddenMask) == 0: No bit set in forbiddenMask can be set in S.

Among all subarrays satisfying these conditions, your task is to return the maximum possible XOR sum S. If no such subarray exists, return -1.

Input & output

  • nums: An array of non-negative integers.
  • targetMask: An integer representing the bits that must be set in the subarray XOR sum.
  • forbiddenMask: An integer representing the bits that must not be set in the subarray XOR sum.
  • Return: A number representing the maximum possible XOR sum S that satisfies the conditions. Return -1 if no such subarray exists.

Clarifications

  • Empty array / Single element: A subarray can consist of a single element (L=R). An empty array nums is not possible per constraints.
  • No valid subarray: If no subarray's XOR sum meets the criteria, return -1.
  • Overlapping Masks: If targetMask and forbiddenMask have common bits set (i.e., (targetMask & forbiddenMask) != 0), it's impossible to satisfy both conditions for any XOR sum. In this case, you should return -1 immediately.

Examples

1

Example 1

Input:

nums = [1, 2, 3, 4], targetMask = 1, forbiddenMask = 0

Output:

7

Note:

The subarray [3, 4] has an XOR sum of 3 ^ 4 = 7. Conditions check: (7 & 1) == 1 (True) and (7 & 0) == 0 (True). This is the maximum such XOR sum. For example, [1,2] has XOR sum 3, which is valid but smaller.

2

Example 2

Input:

nums = [5, 10, 15], targetMask = 2, forbiddenMask = 1

Output:

10

Note:

targetMask = 010_2, forbiddenMask = 001_2. (targetMask & forbiddenMask) == 0, so conditions are not contradictory. The subarray [10] has an XOR sum of 10. Conditions check: (10 & 2) == 2 (True) and (10 & 1) == 0 (True). This is the maximum possible. For instance, [5] has XOR sum 5 (101_2), but (5 & 2) == 0 (violates targetMask) and (5 & 1) == 1 (violates forbiddenMask).

3

Example 3

Input:

nums = [7, 14, 21], targetMask = 4, forbiddenMask = 1

Output:

14

Note:

targetMask = 100_2, forbiddenMask = 001_2. (targetMask & forbiddenMask) == 0, so conditions are not contradictory. The subarray [14] has an XOR sum of 14. Conditions check: (14 & 4) == 4 (True) and (14 & 1) == 0 (True). This is the maximum possible. For instance, [7] has XOR sum 7 (111_2), but (7 & 1) == 1 (violates forbiddenMask).

4

Example 4

Input:

nums = [10, 20], targetMask = 1, forbiddenMask = 0

Output:

-1

Note:

Subarray [10]: XOR sum = 10 (1010_2). (10 & 1) == 0, fails targetMask. Subarray [20]: XOR sum = 20 (10100_2). (20 & 1) == 0, fails targetMask. Subarray [10, 20]: XOR sum = 10 ^ 20 = 26 (11010_2). (26 & 1) == 0, fails targetMask. No valid subarray found, so return -1.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < 2^30
  • 0 <= targetMask < 2^30
  • 0 <= forbiddenMask < 2^30
  • The solution should aim for optimal time complexity, ideally O(N * BITS) where BITS is the number of bits (approximately 30 for values less than 2^30).
  • Space complexity should be reasonable, ideally O(N * BITS).

What interviewers evaluate

  • Correctness of the bitwise logic for handling targetMask and forbiddenMask during the search.
  • Efficient use of a data structure (e.g., a Bit-Trie or XOR Trie) to optimize subarray XOR sum queries.
  • Accurate handling of edge cases, including the (targetMask & forbiddenMask) != 0 scenario and cases where no valid subarray exists.
  • Overall time and space complexity, ensuring the solution scales efficiently for N = 10^5.

Loading editor...