MediumTrieAI interview only
Count Subarrays With XOR Less Than K
Asked atgoogleamazonmicrosoft
01 · Problem
Given an integer array nums and an integer k, return the number of contiguous non-empty subarrays whose bitwise XOR of all elements is strictly less than k.
02 · Examples
Example 01
Input
nums = [1,2,3], k = 3
Output
4
Subarray XORs are [1]=1, [2]=2, [3]=3, [1,2]=3, [2,3]=1, [1,2,3]=0. Four of them (1, 2, 1, 0) are below 3.
Example 02
Input
nums = [4,1,3,2], k = 5
Output
8
The XORs 4, 1, 3, 2, 1^3=2, 3^2=1, 1^3^2=0 and 4^1^3^2=4 are all below 5; only 4^1=5 and 4^1^3=6 are not.
Example 03
Input
nums = [5,5,5], k = 1
Output
2
Only a XOR of 0 is below 1, which happens for the two subarrays [5,5].
03 · Constraints
- 011 <= nums.length <= 105
- 020 <= nums[i] < 220
- 030 <= k <= 220
04 · Optimal complexity
- Time
- O(n * B)
- Space
- O(n * B)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.