Number of Subarrays With AND Value of K solution and explanation
6 more videos on this problem
3209. Number of Subarrays With AND Value of K | Bit Manipulation | Arrays | Hash MapAryan Mittal · 22:05 · 4K views
3209. Number of Subarrays With AND Value of K | Leetcode Biweekly 134codingMohan · 28:22 · 1K views
3209. Number of Subarrays With AND Value of K (Leetcode Hard)Programming Live with Larry · 26:08 · 526 views
3209. Number of Subarrays With AND Value of K | Leetcode Biweekly Contest 134Amit Choraria · 15:36 · 109 views
3209. Number of Subarrays With AND Value of K (leetcode hard)Coder on A Farm · 6:34 · 64 views
3209. Number of Subarrays With AND Value of K | Binary Search | Day1: Final75 Challenge | LeetcodeCodeNow - By Gopal Gupta · 22:25 · 55 views
LeetCode: 3209 Number of Subarrays With AND Value of Kpst.community · 7:24 · 46 views
The problem
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.
def count_subarrays_with_and(nums, k):
count = 0
n = len(nums)
for i in range(n):
and_value = nums[i]
for j in range(i, n):
and_value &= nums[j]
if and_value == k:
count += 1
return count
nums = [1, 1, 2]
k = 1
print(count_subarrays_with_and(nums, k))import java.util.*;
public class Main {
public static int countSubarraysWithAND(int[] nums, int k) {
int count = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
int andValue = nums[i];
for (int j = i; j < n; j++) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 1, 2};
int k = 1;
System.out.println(countSubarraysWithAND(nums, k));
}
}#include <iostream>
#include <vector>
using namespace std;
int countSubarraysWithAND(vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
int andValue = nums[i];
for (int j = i; j < n; ++j) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums = {1, 1, 2};
int k = 1;
cout << countSubarraysWithAND(nums, k) << endl;
return 0;
}function countSubarraysWithAND(nums, k) {
let count = 0;
let n = nums.length;
for (let i = 0; i < n; i++) {
let andValue = nums[i];
for (let j = i; j < n; j++) {
andValue &= nums[j];
if (andValue === k) {
count++;
}
}
}
return count;
}
console.log(countSubarraysWithAND([1, 1, 2], 1));#include <stdio.h>
int countSubarraysWithAND(int* nums, int numsSize, int k) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
int andValue = nums[i];
for (int j = i; j < numsSize; j++) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 1, 2};
int k = 1;
int result = countSubarraysWithAND(nums, 3, k);
printf("%d\n", result);
return 0;
}using System;
class Program {
static int CountSubarraysWithAND(int[] nums, int k) {
int count = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
int andValue = nums[i];
for (int j = i; j < n; j++) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
static void Main() {
int[] nums = {1, 1, 2};
int k = 1;
Console.WriteLine(CountSubarraysWithAND(nums, k));
}
}The Python solution implements the brute force method by iterating over all subarrays and calculating the AND value, comparing it to k. The count is incremented for any matches.
Time Complexity: O(n^2), iterating over all pairs of indices.
Space Complexity: O(1), with no additional structures.
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.
def count_subarrays_with_and(nums, k):
count = 0
n = len(nums)
for i in range(n):
if nums[i] == k:
count += 1
and_value = nums[i]
for j in range(i + 1, n):
and_value &= nums[j]
if and_value == k:
count += 1
return count
nums = [1, 2, 3]
k = 2
print(count_subarrays_with_and(nums, k))public class Main {
public static int countSubarraysWithAND(int[] nums, int k) {
int count = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] == k) count++;
int andValue = nums[i];
for (int j = i + 1; j < n; j++) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
int k = 2;
System.out.println(countSubarraysWithAND(nums, k));
}
}#include <iostream>
#include <vector>
using namespace std;
int countSubarraysWithAND(vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] == k) count++;
int andValue = nums[i];
for (int j = i + 1; j < n; ++j) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums = {1, 2, 3};
int k = 2;
cout << countSubarraysWithAND(nums, k) << endl;
return 0;
}function countSubarraysWithAND(nums, k) {
let count = 0;
let n = nums.length;
for (let i = 0; i < n; i++) {
if (nums[i] === k) count++;
let andValue = nums[i];
for (let j = i + 1; j < n; j++) {
andValue &= nums[j];
if (andValue === k) {
count++;
}
}
}
return count;
}
console.log(countSubarraysWithAND([1, 2, 3], 2));#include <stdio.h>
int countSubarraysWithAND(int* nums, int numsSize, int k) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == k) count++;
int andValue = nums[i];
for (int j = i + 1; j < numsSize; j++) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 2, 3};
int k = 2;
int result = countSubarraysWithAND(nums, 3, k);
printf("%d\n", result);
return 0;
}using System;
class Program {
static int CountSubarraysWithAND(int[] nums, int k) {
int count = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
if (nums[i] == k) count++;
int andValue = nums[i];
for (int j = i + 1; j < n; j++) {
andValue &= nums[j];
if (andValue == k) {
count++;
}
}
}
return count;
}
static void Main() {
int[] nums = {1, 2, 3};
int k = 2;
Console.WriteLine(CountSubarraysWithAND(nums, k));
}
}This Python code moves through the elements using a sliding window technique, thereby efficiently finding and counting subarrays based on their AND value and the given threshold k.
Time Complexity: Close to O(n), as it optimizes AND checks using an adaptive slide.
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.
function countSubarrays(nums: number[], k: number): number {
let ans = 0;
let pre = new Map<number, number>();
for (const x of nums) {
const cur = new Map<number, number>();
for (const [y, v] of pre) {
const z = x & y;
cur.set(z, (cur.get(z) || 0) + v);
}
cur.set(x, (cur.get(x) || 0) + 1);
ans += cur.get(k) || 0;
pre = cur;
}
return ans;
}func countSubarrays(nums []int, k int) (ans int64) {
pre := map[int]int{}
for _, x := range nums {
cur := map[int]int{}
for y, v := range pre {
cur[x&y] += v
}
cur[x]++
ans += int64(cur[k])
pre = cur
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), iterating over all pairs of indices. |
| Optimized Sliding Window Approach | Time Complexity: Close to O(n), as it optimizes AND checks using an adaptive slide. |
| Hash Table + Enumeration | – |
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 |
Frequently asked questions
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.