🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve this problem, we need to understand the bitwise AND operation. The bitwise AND of a subarray is calculated by ANDing all the elements in the subarray. Our goal is to find subarrays where this AND operation results in the integer k
.
The key insight is that the bitwise AND of any number with k
will retain the bits of k
only if those bits are present in the number. Hence, we can utilize a hashmap to keep track of all possible bitwise AND results up to the current index and their frequencies.
Approach
- Initialization: Start by initializing a hashmap
map
to keep track of the count of all bitwise AND results encountered so far. Also, initialize a variableres
to store the count of valid subarrays. - Iterate through the array: For each element in the array, update a temporary hashmap
map2
with new bitwise AND results formed by ANDing the current element with all keys inmap
. - Update the current element in the hashmap: Additionally, add the current element itself to
map2
with a count of 1. - Update the main hashmap: Replace
map
withmap2
at the end of each iteration. - Count the valid subarrays: For each iteration, add the count of subarrays with the bitwise AND result equal to
k
(if present in the hashmap) tores
. - Return the result: Finally, return
res
as the count of subarrays with bitwise AND equal tok
.
Complexity
- Time Complexity: O(n * m), where
n
is the number of elements in the array andm
is the number of unique bitwise AND results encountered so far. In the worst case,m
can be the same asn
, resulting in O(n^2) complexity. - Space Complexity: O(m), where
m
is the number of unique bitwise AND results. This space is used by the hashmap to store the counts of bitwise AND results.
Code Explanation
Variable Initialization
var map = {};
var res = 0;
map
: A hashmap initialized to store bitwise AND results and their counts.res
: A variable initialized to store the count of valid subarrays where bitwise AND equalsk
.
Main Loop Through Array
for (var x of nums) {
- Iterate through each element
x
in thenums
array.
Nested Loop for Previous Map
var map2 = {};
for (var y in map) {
map2[y & x] = (map2[y & x] || 0) + map[y];
}
- Create a new hashmap
map2
to store updated bitwise AND results for the current elementx
. - Iterate through the keys
y
of themap
hashmap. - Calculate the bitwise AND of
y
andx
, updatingmap2
with the count frommap
.
Update Map2 with Current Element
map2[x] = (map2[x] || 0) + 1;
- Update
map2
with the current elementx
itself, counting it once.
Update Main Map
map = map2;
- Update the main
map
hashmap tomap2
for the next iteration.
Count Valid Subarrays
res += map[k] || 0;
- Add the count of subarrays where the bitwise AND equals
k
frommap
tores
.
Return Result
return res;
- Return
res
, which contains the total count of subarrays where bitwise AND equalsk
.
Code
C++
class Solution {
public:
long long countSubarrays(vector& nums, int k) {
unordered_map map;
long long res = 0;
for (int x : nums) {
unordered_map map2;
for (auto& [y, count] : map) {
map2[y & x] += count;
}
map2[x] += 1;
map = map2;
res += map[k];
}
return res;
}
};
Python
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
map = {}
res = 0
for x in nums:
map2 = {}
for y in map:
map2[y & x] = map2.get(y & x, 0) + map[y]
map2[x] = map2.get(x, 0) + 1
map = map2
res += map.get(k, 0)
return res
Java
class Solution {
public long countSubarrays(int[] nums, int k) {
Map map = new HashMap<>();
long res = 0;
for (int x : nums) {
Map map2 = new HashMap<>();
for (int y : map.keySet()) {
map2.put(y & x, map2.getOrDefault(y & x, 0L) + map.get(y));
}
map2.put(x, map2.getOrDefault(x, 0L) + 1);
map = map2;
res += map.getOrDefault(k, 0L);
}
return res;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var countSubarrays = function (nums, k) {
var map = {};
var res = 0;
for (var x of nums) {
var map2 = {};
for (var y in map) {
map2[y & x] = (map2[y & x] || 0) + map[y];
}
map2[x] = (map2[x] || 0) + 1;
map = map2;
res += map[k] || 0;
}
return res;
};