Number of Subarrays With AND Value of K - Video Solutions

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.