Number of Subarrays With AND Value of K

Number of Subarrays With AND Value of K

What is this problem about?

The Number of Subarrays With AND Value of K problem asks you to count subarrays where the bitwise AND of all elements equals exactly k. This hard coding problem leverages the property that AND can only decrease or stay the same as the window grows, enabling efficient enumeration of distinct AND values.

Why is this asked in interviews?

DE Shaw asks this because it requires the non-trivial observation that for any fixed right endpoint, the number of distinct AND values of subarrays ending there is O(log(max_value)). This allows efficient enumeration using a "compressed AND value tracking" technique. The array, binary search, bit manipulation, and segment tree interview pattern is the core.

Algorithmic pattern used

AND compression with right endpoint scan. For each right endpoint j, maintain a set of (AND_value, leftmost_start) pairs for all subarrays ending at j. When extending to j+1: AND each existing value with nums[j+1] and merge equal values (taking the minimum start). Since AND can only decrease or stay, distinct values are O(log max_val). For each entry with AND=k, count the valid start positions.

Example explanation

nums=[1,1,2,3], k=1.

• j=0: pairs=[(1,0)]. AND=1=k, count=1 subarray [1..0].
• j=1: extend: [(1&1,0)]=[(1,0)]. New: [(1,1)]. Merged: [(1,0)]. AND=1=k, spans [0..1] and [1..1], count=2.
• j=2: extend: [(1&2,0)]=[(0,0)]. New: [(2,2)]. pairs=[(0,0),(2,2)]. k=1 not found, count=0.
• j=3: extend: [(0&3,0),(2&3,2)]=[(0,0),(2,2)]. New: [(3,3)]. k=1 not found. Total = 1+2 = 3.

Common mistakes candidates make

• O(n²) brute force (too slow for large arrays).
• Not merging duplicate AND values (keeping separate entries for the same AND value).
• Confusing the "AND decreases monotonically" property with the specific bit patterns.
• Not correctly counting subarrays when multiple start positions share the same AND value.

Interview preparation tip

AND/OR subarray counting problems exploit the O(log max_val) distinct values property: AND can only decrease as the window grows. This "at most O(log max_val) distinct values" insight applies to XOR, OR, and AND operations on subarrays with fixed endpoints. Practice problems involving "count subarrays with OR/AND/XOR equal to k" — they all use this compressed distinct-values technique from a fixed endpoint.