3209. Number of Subarrays With AND Value of K

Given an array of integers nums and an integer k, return the number of subarrays of nums where the bitwise AND of the elements of the subarray equals k.

Example 1:

Input: nums = [1,1,1], k = 1

Output: 6

Explanation:

All subarrays contain only 1's.

Example 2:

Input: nums = [1,1,2], k = 1

Output: 3

Explanation:

Subarrays having an AND value of 1 are: [**1**,1,2], [1,**1**,2], [**1,1**,2].

Example 3:

Input: nums = [1,2,3], k = 2

Output: 2

Explanation:

Subarrays having an AND value of 2 are: [1,**2**,3], [1,**2,3**].

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i], k <= 109

Solution:

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int n = nums.length;
        long count = 0;

        // DP map to store AND values and their counts
        HashMap<Integer, Integer> dp = new HashMap<>();

        for (int i = 0; i < n; i++) {
            HashMap<Integer, Integer> newDp = new HashMap<>();

            // Every element by itself is a subarray
            newDp.put(nums[i], newDp.getOrDefault(nums[i], 0) + 1);

            // Update the map based on the previous subarray's AND values
            for (int key : dp.keySet()) {
                int andValue = key & nums[i];
                newDp.put(andValue, newDp.getOrDefault(andValue, 0) + dp.get(key));
            }

            // Count the subarrays with AND value equal to k
            count += newDp.getOrDefault(k, 0);

            // Update the dp map for the next iteration
            dp = newDp;
        }

        return count;
    }
}