Number of Subarrays With AND Value of K
HardPrompt
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 <= 1050 <= nums[i], k <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a counter
countto 0. - Iterate through the array with an outer loop using index
ifrom 0 ton-1to mark the start of a subarray. - Inside the outer loop, initialize a variable
currentAndto-1(which represents a number with all bits set to 1, the identity for the bitwise AND operation). - Start an inner loop with index
jfromiton-1to mark the end of the subarray. - In the inner loop, update
currentAndby performing a bitwise AND with the current elementnums[j]. (currentAnd &= nums[j]) - Check if the
currentAndis equal tok. If it is, increment thecount. - After the loops complete, return
count.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
totalCount = 0Land a HashMapprevAndsto store the AND values of subarrays ending at the previous index and their frequencies. - Iterate through each
numin the input arraynums. - For each
num, create a new HashMapcurrentAnds. - If
numitself is equal tok, incrementtotalCount. This handles subarrays of length one. - Add
numtocurrentAndswith a frequency of 1. - Iterate through each
(value, frequency)pair inprevAnds.- Calculate the new AND value:
newAnd = value & num. - If
newAndequalsk, addfrequencytototalCount. - Update the frequency of
newAndincurrentAndsby addingfrequency.
- Calculate the new AND value:
- After processing all pairs from
prevAnds, replaceprevAndswithcurrentAndsfor the next iteration. - Return
totalCount.
Walkthrough
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.
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<Integer, Integer> prevAnds = new HashMap<>(); for (int num : nums) { Map<Integer, Integer> 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<Integer, Integer> 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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
class Solution {public long countSubarrays(int[] nums, int k) { long ans = 0; Map<Integer, Integer> pre = new HashMap<>(); for (int x : nums) { Map<Integer, Integer> 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; }}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 ansclass Solution {public: long long countSubarrays(vector<int> &nums, int k) { long long ans = 0; unordered_map<int, int> pre; for (int x : nums) { unordered_map<int, int> cur; for (auto &[y, v] : pre) { cur[x & y] += v; } cur[x]++; ans += cur[k]; pre = cur; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.