Number of Subarrays With AND Value of K

Problem Description

Ah, the classic “Number of Subarrays With AND Value of K” problem! It’s like trying to find a needle in a haystack, but instead of a needle, you’re looking for subarrays that, when you apply the AND operation, magically equal a specific number, K. Imagine you’re at a party, and you’re trying to find that one friend who can only be found if they’re standing next to someone who’s also wearing a blue shirt. That’s basically what this problem is asking you to do with numbers!

In simpler terms, given an array of integers, you need to count how many contiguous subarrays have an AND value equal to K. If you think that sounds easy, just wait until you try it!

Code Solution


class Solution {
    public long countSubarrays(int[] nums, int k) {
        long ans = 0;
        Map prev = new HashMap<>();

        for (final int num : nums) {
            Map curr = new HashMap<>() {
                { put(num, 1); }
            };
            for (Map.Entry entry : prev.entrySet()) {
                final int val = entry.getKey();
                final int freq = entry.getValue();
                curr.merge(val & num, freq, Integer::sum);
            }
            ans += curr.getOrDefault(k, 0);
            prev = curr;
        }

        return ans;
    }
}

Approach Explanation

The code uses a HashMap to keep track of the frequency of AND values of subarrays ending at each number. For each number in the array, it creates a new map (curr) to store the AND values and their frequencies. It then merges the current number with the previous AND values, extending the subarrays. Finally, it checks if the AND value equals K and updates the answer accordingly.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * m)
Space Complexity	O(m)

Real-World Example

Imagine you’re at a buffet, and you can only eat dishes that have a specific combination of ingredients (let’s say K). You’re trying to find all the combinations of dishes that meet your criteria. Each dish represents a number in the array, and the AND operation is like checking if the ingredients match your requirements. The solution helps you count how many combinations (subarrays) you can enjoy without breaking your dietary rules!