3209. Number of Subarrays With AND Value of K

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

1. 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.
2. 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.
3. Update the current element in the hashmap: Additionally, add the current element itself to map2 with a count of 1.
4. Update the main hashmap: Replace map with map2 at the end of each iteration.
5. 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.
6. Return the result: Finally, return res as the count of subarrays with bitwise AND equal to k.

Complexity

• Time Complexity: O(n * m), where 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.
• 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 equals k.

Main Loop Through Array

  for (var x of nums) {

• Iterate through each element x in the nums 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 element x.
• Iterate through the keys y of the map hashmap.
• Calculate the bitwise AND of y and x, updating map2 with the count from map.

Update Map2 with Current Element

map2[x] = (map2[x] || 0) + 1;

• Update map2 with the current element x itself, counting it once.

Update Main Map

map = map2;

• Update the main map hashmap to map2 for the next iteration.

Count Valid Subarrays

res += map[k] || 0;

• Add the count of subarrays where the bitwise AND equals k from map to res.

Return Result

return res;

• Return res, which contains the total count of subarrays where bitwise AND equals k.

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;
};