Number of Subarrays With AND Value of K — Problem & Solution
Number of Subarrays With AND Value of K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Subarrays With AND Value of K is a hard coding problem on arrays, binary search and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Bit Manipulation, Segment Tree
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums and an integer k, return the number of non-empty contiguous subarrays whose bitwise AND of all elements equals k.
CodeKairo bound: the original allows 10^5 elements, whose answer needs 64 bits; here nums.length <= 5 * 10^4, so the answer fits a 32-bit integer.
Example 1
Input: nums = [7,3,3,1], k = 3
Output: 5
Explanation: `[3]` twice, `[3,3]`, `[7,3]` and `[7,3,3]`.
Example 2
Input: nums = [4,4], k = 0
Output: 0
Example 3
Input: nums = [2,1,3], k = 0
Output: 2
Explanation: `[2,1]` and `[2,1,3]`.
Constraints
1 <= nums.length <= 5 * 10^40 <= nums[i], k <= 10^9
Hints for Number of Subarrays With AND Value of K
Hint 1
Fix the right end
jand let the left end move left: the AND can only lose bits.Hint 2
Each time the AND changes it loses at least one of at most 30 bits, so the subarrays ending at
jproduce at most 31 distinct AND values.Hint 3
Keep, for each
j, the list of distinct AND values of subarrays ending atjwith how many subarrays give each; build the list forj + 1from the one forj.
How to solve Number of Subarrays With AND Value of K
The ANDs of all subarrays ending at a fixed index take at most 31 distinct values, so carrying a compressed list of (value, count) pairs from one index to the next counts every subarray in O(30) per element.
Approach
- Keep a list of pairs
(value, count): the distinct ANDs of subarrays ending at the previous index, ordered by start position. - For the new element
x, replace every valuevbyv AND x, merging neighbours that become equal (they are adjacent because the ANDs only grow as the start moves right), then append(x, 1)for the subarray[x]itself, merging it too. - Add the count of the pair whose value equals
k(if any) to the answer.
Why it works
Every subarray ending at j is represented in the list exactly once through its count, because extending all subarrays ending at j - 1 by nums[j] and adding the single-element subarray produces exactly the subarrays ending at j. A value can only drop bits as the start moves left, so there are at most 31 distinct values, keeping each step O(30).
Complexity
- Time —
O(30 · n) - Space —
O(30)
Pitfalls
- Counting distinct values is not enough — keep how many subarrays share each value.
kmay be 0; zeros innumsmake every subarray through them AND to 0.- The O(n²) double loop works but is too slow for 5 · 10^4 elements in the slower languages.
Reference solution
Python
from typing import List
def countSubarrays(nums: List[int], k: int) -> int:
vals = []
cnts = []
total = 0
for x in nums:
nv = []
nc = []
for v, c in zip(vals, cnts):
w = v & x
if nv and nv[-1] == w:
nc[-1] += c
else:
nv.append(w)
nc.append(c)
if nv and nv[-1] == x:
nc[-1] += 1
else:
nv.append(x)
nc.append(1)
vals, cnts = nv, nc
for v, c in zip(vals, cnts):
if v == k:
total += c
return totalJava
public static int countSubarrays(int[] nums, int k) {
int[] vals = new int[33], cnts = new int[33];
int[] nv = new int[33], nc = new int[33];
int len = 0;
long total = 0;
for (int x : nums) {
int nl = 0;
for (int t = 0; t < len; t++) {
int w = vals[t] & x;
if (nl > 0 && nv[nl - 1] == w) nc[nl - 1] += cnts[t];
else { nv[nl] = w; nc[nl] = cnts[t]; nl++; }
}
if (nl > 0 && nv[nl - 1] == x) nc[nl - 1] += 1;
else { nv[nl] = x; nc[nl] = 1; nl++; }
int[] tmp = vals; vals = nv; nv = tmp;
tmp = cnts; cnts = nc; nc = tmp;
len = nl;
for (int u = 0; u < len; u++) if (vals[u] == k) total += cnts[u];
}
return (int) total;
}C++
int countSubarrays(vector<int>& nums, int k) {
vector<pair<int, int>> cur, nxt;
long long total = 0;
for (int x : nums) {
nxt.clear();
for (auto& p : cur) {
int w = p.first & x;
if (!nxt.empty() && nxt.back().first == w) nxt.back().second += p.second;
else nxt.push_back(make_pair(w, p.second));
}
if (!nxt.empty() && nxt.back().first == x) nxt.back().second += 1;
else nxt.push_back(make_pair(x, 1));
swap(cur, nxt);
for (auto& p : cur) if (p.first == k) total += p.second;
}
return (int) total;
}JavaScript
var countSubarrays = function(nums, k) {
var vals = [], cnts = [], total = 0;
for (var i = 0; i < nums.length; i++) {
var x = nums[i], nv = [], nc = [];
for (var t = 0; t < vals.length; t++) {
var w = vals[t] & x;
if (nv.length && nv[nv.length - 1] === w) nc[nc.length - 1] += cnts[t];
else { nv.push(w); nc.push(cnts[t]); }
}
if (nv.length && nv[nv.length - 1] === x) nc[nc.length - 1] += 1;
else { nv.push(x); nc.push(1); }
vals = nv;
cnts = nc;
for (var u = 0; u < vals.length; u++) if (vals[u] === k) total += cnts[u];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search