# Number of Subarrays With AND Value of K **Difficulty:** HARD [External](https://leetcode.com/problems/number-of-subarrays-with-and-value-of-k) Canonical: https://scaleengineer.com/dsa/problems/number-of-subarrays-with-and-value-of-k **Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** Array, Segment Tree **Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw) --- ## Problem 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` # Approaches ## Brute Force with Optimization The brute-force approach is the most straightforward solution. It involves generating every possible subarray, calculating the bitwise AND of its elements, and checking if this value equals `k`. We increment a counter for each subarray that satisfies the condition. **Time:** O(N^2), where N is the number of elements in the array. The two nested loops lead to a quadratic runtime. · **Space:** O(1) extra space, as we only use a few variables to store the count and the running AND value. **Pros:** Simple to understand and implement.; Requires no extra space, aside from a few variables. **Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms. ### Explanation This approach uses two nested loops to consider every possible subarray. The outer loop fixes the starting index `i`, and the inner loop iterates from `i` to the end of the array, defining the ending index `j`. For each starting index `i`, we maintain a `currentAnd` variable that holds the bitwise AND of elements from `nums[i]` to `nums[j]`. As we extend the subarray by incrementing `j`, we update `currentAnd` by ANDing it with `nums[j]`. If at any point `currentAnd` equals `k`, we've found a valid subarray and increment our total count. The total count can exceed the capacity of a 32-bit integer, so we use a `long` to store the result. ```java class Solution { public long countSubarrays(int[] nums, int k) { int n = nums.length; long count = 0; for (int i = 0; i < n; i++) { int currentAnd = -1; // Represents all bits set to 1 for (int j = i; j < n; j++) { currentAnd &= nums[j]; if (currentAnd == k) { count++; } } } return count; } } ``` ### Algorithm * Initialize a counter `count` to 0. * Iterate through the array with an outer loop using index `i` from 0 to `n-1` to mark the start of a subarray. * Inside the outer loop, initialize a variable `currentAnd` to `-1` (which represents a number with all bits set to 1, the identity for the bitwise AND operation). * Start an inner loop with index `j` from `i` to `n-1` to mark the end of the subarray. * In the inner loop, update `currentAnd` by performing a bitwise AND with the current element `nums[j]`. (`currentAnd &= nums[j]`) * Check if the `currentAnd` is equal to `k`. If it is, increment the `count`. * After the loops complete, return `count`. ## Dynamic Programming with Value Compression A highly efficient approach can be designed by observing a key property of the bitwise AND operation. As we extend a subarray to the right, its bitwise AND value is monotonically non-increasing. This implies that for any fixed ending position `j`, the set of distinct AND values for all subarrays `nums[i...j]` (where `i <= j`) is very small. Specifically, the number of distinct values is bounded by the number of bits in the integers (e.g., around 30 for numbers up to 10^9). We can leverage this by using a dynamic programming approach, where we maintain the frequencies of these distinct AND values as we iterate through the array. **Time:** O(N * log(M)), where N is the length of `nums` and M is the maximum value. For each element, we iterate through the distinct AND values from the previous step. The number of such values is at most `log(M)`. · **Space:** O(log(M)), where M is the maximum possible value in `nums`. The HashMaps store at most `log(M)` distinct AND values at any time, which is a small constant (around 30). **Pros:** Very efficient, with a time complexity that is near-linear.; Passes the given constraints with ease.; Uses minimal extra space. **Cons:** The logic is more complex compared to the brute-force approach.; Requires careful implementation to handle the state transfer between iterations correctly. ### Explanation We iterate through the array, and for each element `nums[j]`, we calculate the AND values of all subarrays ending at `j`. We can do this efficiently by using the results from the previous step `j-1`. Let's maintain a map, `prevAnds`, storing the distinct AND values of subarrays ending at `j-1` and their counts. When we move to `nums[j]`, we can compute the new set of AND values. A subarray ending at `j` is either the single element `[nums[j]]` or a subarray ending at `j-1` extended with `nums[j]`. So, for each `(value, count)` in `prevAnds`, the new AND value becomes `value & nums[j]`. We accumulate these new values and their counts in a `currentAnds` map. We also add `nums[j]` to `currentAnds` for the subarray of length one. While building `currentAnds`, we check if any of the new AND values equal `k` and update our total count accordingly. After processing `nums[j]`, `currentAnds` becomes `prevAnds` for the next step. ```java import java.util.HashMap; import java.util.Map; class Solution { public long countSubarrays(int[] nums, int k) { long totalCount = 0; // Map from a previous AND value to the number of subarrays ending at the last element with that AND value. Map prevAnds = new HashMap<>(); for (int num : nums) { Map currentAnds = new HashMap<>(); // Case 1: The subarray is just the current number itself. if (num == k) { totalCount++; } currentAnds.put(num, 1); // Case 2: Extend all previous subarrays with the current number. for (Map.Entry entry : prevAnds.entrySet()) { int prevValue = entry.getKey(); int frequency = entry.getValue(); int newAnd = prevValue & num; if (newAnd == k) { totalCount += frequency; } currentAnds.put(newAnd, currentAnds.getOrDefault(newAnd, 0) + frequency); } prevAnds = currentAnds; } return totalCount; } } ``` ### Algorithm * Initialize `totalCount = 0L` and a HashMap `prevAnds` to store the AND values of subarrays ending at the previous index and their frequencies. * Iterate through each `num` in the input array `nums`. * For each `num`, create a new HashMap `currentAnds`. * If `num` itself is equal to `k`, increment `totalCount`. This handles subarrays of length one. * Add `num` to `currentAnds` with a frequency of 1. * Iterate through each `(value, frequency)` pair in `prevAnds`. * Calculate the new AND value: `newAnd = value & num`. * If `newAnd` equals `k`, add `frequency` to `totalCount`. * Update the frequency of `newAnd` in `currentAnds` by adding `frequency`. * After processing all pairs from `prevAnds`, replace `prevAnds` with `currentAnds` for the next iteration. * Return `totalCount`. # Solutions ### Java ```java class Solution { public long countSubarrays(int[] nums, int k) { long ans = 0; Map pre = new HashMap<>(); for (int x : nums) { Map cur = new HashMap<>(); for (var e : pre.entrySet()) { int y = e.getKey(), v = e.getValue(); cur.merge(x & y, v, Integer : : sum); } cur.merge(x, 1, Integer : : sum); ans += cur.getOrDefault(k, 0); pre = cur; } return ans; } } ``` ### Python ```python class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: ans = 0 pre = Counter() for x in nums: cur = Counter() for y, v in pre . items(): cur[x & y] += v cur[x] += 1 ans += cur[k] pre = cur return ans ``` ### CPP ```cpp class Solution { public: long long countSubarrays(vector &nums, int k) { long long ans = 0; unordered_map pre; for (int x : nums) { unordered_map cur; for (auto &[y, v] : pre) { cur[x & y] += v; } cur[x]++; ans += cur[k]; pre = cur; } return ans; } }; ```