Given an array of positive integers nums of length n and a non‑negative integer k.
Return the number of contiguous subarrays whose bitwise XOR of all elements is greater than or equal to k.
Example 1:
Input: nums = [3,1,2,3], k = 2
Output: 6
Explanation:
The valid subarrays with XOR >= 2 are [3] at index 0, [3, 1] at indices 0 - 1, [3, 1, 2, 3] at indices 0 - 3, [1, 2] at indices 1 - 2, [2] at index 2, and [3] at index 3; there are 6 in total.
Example 2:
Input: nums = [0,0,0], k = 0
Output: 6
Explanation:
Every contiguous subarray yields XOR = 0, which meets k = 0. There are 6 such subarrays in total.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= k <= 109Problem Overview: Given an array of integers and a value k, count how many subarrays have a bitwise XOR greater than or equal to k. A direct enumeration quickly becomes too slow, so the goal is to compute these counts efficiently using prefix properties of XOR.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Compute the XOR for every possible subarray. Start at index i, extend the subarray to j, and update a running XOR as you iterate forward. Each time the XOR becomes >= k, increment the count. This approach leverages the incremental nature of XOR but still evaluates all n(n+1)/2 subarrays. Time complexity is O(n²) and space complexity is O(1). It works for small arrays but fails under typical competitive programming constraints.
Approach 2: Prefix XOR + Binary Trie (O(n log M) time, O(n log M) space)
The optimized approach relies on the prefix XOR idea: the XOR of a subarray [l, r] equals prefix[r] ^ prefix[l-1]. Instead of checking every pair, maintain previously seen prefix XOR values inside a binary trie. For the current prefix px, you want the number of earlier prefixes p where px ^ p >= k. The trie stores prefix values bit by bit (usually 31–32 bits). While traversing the trie, compare each bit of px with the corresponding bit of k to count valid branches that guarantee the XOR threshold is satisfied.
Each insertion and query touches at most the number of bits in the integer (typically 31). That gives O(log M) work per element, where M is the maximum integer value. Processing all prefixes results in O(n log M) time and O(n log M) space for the trie. This technique combines prefix sum style reasoning with bitwise comparison inside a trie, making it a common pattern in advanced bit manipulation problems.
Recommended for interviews: Interviewers expect the prefix XOR + trie solution. Showing the brute force first demonstrates you understand how XOR behaves across subarrays. Moving to the trie-based counting method shows deeper algorithmic skill and familiarity with bitwise data structures that reduce the search from quadratic to near-linear time.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray XOR | O(n²) | O(1) | Small arrays or quick baseline to verify correctness |
| Prefix XOR + Binary Trie | O(n log M) | O(n log M) | General case for large inputs where subarray enumeration is too slow |
Practice Subarrays with XOR at Least K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor