Skip to main content
Talentd

Subarrays with XOR at Least K - Solution & Explanation

HardPremiumFree on FleetCodeArrayBit ManipulationTriePrefix Sum3 min read
Practice this problem

Problem Statement

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 <= 105
  • 0 <= nums[i] <= 109
  • 0 <= k <= 109

Approach Overview

Problem 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

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray XORO(n²)O(1)Small arrays or quick baseline to verify correctness
Prefix XOR + Binary TrieO(n log M)O(n log M)General case for large inputs where subarray enumeration is too slow

Frequently Asked Questions

Is Subarrays with XOR at Least K easy or hard?
Subarrays with XOR at Least K is considered a hard problem because it combines multiple concepts: prefix XOR, bit manipulation, and trie-based counting. Implementing the trie traversal correctly for inequality conditions requires careful bit-level reasoning.
Subarrays with XOR at Least K Python/Java solution
Typical implementations compute prefix XOR while maintaining a binary trie that stores counts at each node. For every prefix, the algorithm queries the trie to count valid prefixes producing XOR >= K, then inserts the current prefix. The same logic works in Python, Java, C++, and Go with O(n log M) complexity.
How to solve Subarrays with XOR at Least K in O(n)?
Strict O(n) is difficult because comparisons depend on individual bits. The closest practical bound is O(n log M) using a binary trie with prefix XOR values. Each array element performs one trie query and one insertion, and each operation processes around 31 bits.
What is the best approach for Subarrays with XOR at Least K?
The most efficient approach uses prefix XOR combined with a binary trie. Store previously seen prefix XOR values in the trie and, for each new prefix, count how many earlier prefixes produce XOR >= k. Each query and insertion takes O(log M) where M is the maximum integer value, giving an overall time complexity of O(n log M).
Is Subarrays with XOR at Least K asked at Google/Amazon/Meta?
Problems involving prefix XOR and binary tries frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as counting subarrays with XOR less than K or maximum XOR pair use the same core technique and are common in system-level coding interviews.
What data structure is used in Subarrays with XOR at Least K?
The key data structure is a binary trie (also called a bitwise trie). It stores prefix XOR values bit by bit and allows efficient counting of values that satisfy XOR constraints relative to K. The algorithm also relies on the prefix XOR concept from prefix sum techniques.
What is the time complexity of Subarrays with XOR at Least K?
The optimal solution runs in O(n log M) time, where n is the array length and M is the maximum value of elements (typically 2^31 for integers). Each prefix XOR is inserted and queried in a binary trie across its bit representation. The brute force method takes O(n^2) time.

Ready to solve this problem?

Practice Subarrays with XOR at Least K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays