Is Number of Subarrays With AND Value of K easy or hard?

This problem is classified as Hard because counting subarrays with an exact bitwise AND requires understanding how AND behaves across ranges. Recognizing the monotonic property and translating it into a sliding window with bit tracking is the key difficulty.

Number of Subarrays With AND Value of K Python/Java solution

Typical implementations iterate through the array while maintaining bit counts for the current window. The logic is language‑agnostic and works cleanly in Python, Java, C++, or JavaScript because the operations are simple bit checks and pointer updates.

How to solve Number of Subarrays With AND Value of K in O(n)?

Use a sliding window with a small array that tracks how many numbers in the window contain each bit. From these counts you can reconstruct the window's AND quickly. Move the right pointer to expand and the left pointer to shrink while maintaining the AND condition, giving near O(n) time since each pointer moves at most once across the array.

What is the best approach for Number of Subarrays With AND Value of K?

The most efficient approach tracks bit frequencies inside a sliding window. Because the bitwise AND of a window can only decrease when new elements are added, you can maintain the current AND using per-bit counts and adjust the window with two pointers. This reduces the complexity to about O(n · 32), which is effectively linear for typical integer sizes.

Is Number of Subarrays With AND Value of K asked at Google/Amazon/Meta?

Bit manipulation combined with subarray counting patterns appears frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of monotonic bitwise operations, sliding windows, and efficient range aggregation.

What data structure is used in Number of Subarrays With AND Value of K?

The optimized approach mainly uses an array to store bit frequencies along with a two-pointer sliding window. In more advanced variants or repeated queries, a segment tree can be used to compute range AND values efficiently.

What is the time complexity of Number of Subarrays With AND Value of K?

The brute force solution checks every subarray and runs in O(n²) time with O(1) space. The optimized method maintains bit counts for the current window and updates at most 32 bits per pointer move, resulting in O(n · bits) time and O(bits) space.

Description Hints 5 Solution Video 22:05

3209. Number of Subarrays With AND Value of K

Hard35.7% acceptance1 company

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 <= 10⁵
0 <= nums[i], k <= 10⁹

Asked at 1 company

D. E. Shaw

Topics

Hints open one at a time

Hint 1

Let’s say we want to count the number of pairs (l, r) such that nums[l] & nums[l + 1] & … & nums[r] == k.

Hint 2

Fix the left index l.

Hint 3

Note that if you increase r for a fixed l, then the AND value of the subarray either decreases or remains unchanged.

Hint 4

Therefore, consider using binary search.

Hint 5

To calculate the AND value of a subarray, use sparse tables.

22:05

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countSubarrays(self, nums: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,1,1]
1

Input

[1,1,2]
1

Input

[1,2,3]
2

Your code is saved on this device.Solution