Number of Subarrays With AND Value of K - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Given an integer array nums and an integer k, count the number of contiguous subarrays whose bitwise AND equals exactly k. The challenge comes from the behavior of the AND operation: when you extend a subarray, the result can only stay the same or decrease.
Approach 1: Brute Force Enumeration (Time: O(n²), Space: O(1))
Start every subarray at index i and extend it to the right while maintaining the running AND. Initialize current = nums[i], then iterate j = i...n-1 and update current &= nums[j]. Each time the value equals k, increment the answer. Because the AND result only decreases as you expand the subarray, you can stop early once current < k and it cannot become k again. This approach is straightforward and demonstrates the monotonic nature of the bitwise AND operation, but the worst‑case runtime remains quadratic. Useful for small inputs or when validating optimized logic.
Approach 2: Optimized Sliding Window with Bit Tracking (Time: O(n · bits), Space: O(bits))
The key observation: bitwise AND is monotonic when expanding a window. Once a bit becomes 0, it never turns back to 1. Maintain a sliding window and track how many elements in the window contain each bit. Using this frequency array, you can reconstruct the current window AND quickly. Move the right pointer to expand the window and update bit counts; move the left pointer to shrink when the AND drops below the target. To count subarrays with AND exactly equal to k, track windows whose AND is >= k and subtract those with AND > k. Each pointer moves at most n times and each update touches ~32 bits, giving near linear performance.
This technique relies heavily on understanding bit behavior, making it a natural fit for problems involving Bit Manipulation. The array scanning pattern is also a classic application of Array traversal combined with a two‑pointer window. For very large inputs or repeated range queries, similar AND computations can also be supported using structures like a Segment Tree.
Recommended for interviews: Start with the brute force idea to show you understand how subarray AND evolves as the window expands. Interviewers usually expect the optimized sliding window or bit-tracking technique because it reduces the search from O(n²) to near O(n). Demonstrating the monotonic property of AND and translating it into a two‑pointer solution shows strong algorithmic reasoning.
Approach 1: Brute Force Approach
The brute force method involves generating all possible subarrays and computing the AND for each subarray, then checking if it equals to k. It has a high time complexity because all possible subarrays need to be checked.
The provided C code iterates through each subarray, computes the AND value, and compares it with k. If they are equal, the count is incremented. Two nested loops are used, where the outer loop starts each subarray, and the inner loop evaluates its AND starting from the outer loop index.
Complexity
Time Complexity: O(n^2), where n is the number of elements in nums. Each subarray requires constant time operations (AND and comparison).
Space Complexity: O(1), since we only use a constant amount of additional space.
Approach 2: Optimized Sliding Window Approach
The optimized approach uses a sliding window technique to reduce the complexity by maintaining a running AND value and adjusting it as the window slides over the array. This approach is more efficient as it avoids recalculating the AND from scratch for overlapping subarrays.
The solution maintains an AND value for each starting point of the subarray and rights the sequence until the AND result is no longer feasible. Immediate results that match k are counted.
Complexity
Time Complexity: Average case near O(n), where n is the number of elements, if early exits are possible.
Space Complexity: O(1).
Approach 3: Hash Table + Enumeration
According to the problem description, we need to find the result of the bitwise AND operation of elements from index l to r in the array nums, that is, nums[l] \land nums[l + 1] \land cdots \land nums[r], where \land represents the bitwise AND operation.
If we fix the right endpoint r, then the range of the left endpoint l is [0, r]. Since the sum of bitwise AND decreases monotonically as l decreases, and the value of nums[i] does not exceed 10^9, the interval [0, r] can have at most 30 different values. Therefore, we can use a set to maintain all the values of nums[l] \land nums[l + 1] \land cdots \land nums[r] and the number of times these values occur.
When we traverse from r to r+1, the values with r+1 as the right endpoint are the values obtained by performing the bitwise AND operation of each value in the set with nums[r + 1], plus nums[r + 1] itself.
Therefore, we only need to enumerate each value in the set and perform the bitwise AND operation with nums[r] to get all the values and their occurrences with r as the right endpoint. Then, we need to add the occurrence count of nums[r]. At this point, we add the occurrence count of value k to the answer. Continue traversing r until the entire array is traversed.
The time complexity is O(n times log M), and the space complexity is O(log M). Here, n and M are the length of the array nums and the maximum value in the array nums, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the number of elements in |
| Optimized Sliding Window Approach | Time Complexity: Average case near O(n), where n is the number of elements, if early exits are possible. |
| Hash Table + Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n²) | O(1) | Small arrays, debugging logic, or explaining the AND monotonic property in interviews |
| Sliding Window with Bit Frequency Tracking | O(n · bits) | O(bits) | Large inputs where near-linear performance is required; preferred interview solution |
Video Solution
3209. Number of Subarrays With AND Value of K | Bit Manipulation | Arrays | Hash Map • Aryan Mittal • 4,908 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Number of Subarrays With AND Value of K easy or hard?
Number of Subarrays With AND Value of K Python/Java solution
How to solve Number of Subarrays With AND Value of K in O(n)?
What is the best approach for Number of Subarrays With AND Value of K?
Is Number of Subarrays With AND Value of K asked at Google/Amazon/Meta?
What data structure is used in Number of Subarrays With AND Value of K?
What is the time complexity of Number of Subarrays With AND Value of K?
Ready to solve this problem?
Practice Number of Subarrays With AND Value of K with our built-in code editor and test cases.
Practice on FleetCode