Dare2Solve
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.
Initialization: Start by initializing a hashmap map
to keep track of the count of all bitwise AND results encountered so far. Also, initialize a variable res
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 in map
.
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
with map2
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) to res
.
Return the result: Finally, return res
as the count of subarrays with bitwise AND equal to k
.
n
is the number of elements in the array and m
is the number of unique bitwise AND results encountered so far. In the worst case, m
can be the same as n
, resulting in O(n^2) complexity.m
is the number of unique bitwise AND results. This space is used by the hashmap to store the counts of bitwise AND results.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 equals k
. for (var x of nums) {
x
in the nums
array.var map2 = {};
for (var y in map) {
map2[y & x] = (map2[y & x] || 0) + map[y];
}
map2
to store updated bitwise AND results for the current element x
.y
of the map
hashmap.y
and x
, updating map2
with the count from map
.map2[x] = (map2[x] || 0) + 1;
map2
with the current element x
itself, counting it once.map = map2;
map
hashmap to map2
for the next iteration.res += map[k] || 0;
k
from map
to res
.return res;
res
, which contains the total count of subarrays where bitwise AND equals k
.class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
unordered_map<int, long long> map;
long long res = 0;
for (int x : nums) {
unordered_map<int, long long> map2;
for (auto& [y, count] : map) {
map2[y & x] += count;
}
map2[x] += 1;
map = map2;
res += map[k];
}
return res;
}
};
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
class Solution {
public long countSubarrays(int[] nums, int k) {
Map<Integer, Long> map = new HashMap<>();
long res = 0;
for (int x : nums) {
Map<Integer, Long> 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;
}
}
/**
* @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;
};