Number of Subarrays With AND Value of K

Hard
1337.

Number of Subarrays With AND Value of K

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.

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^4
  • 0 <= nums[i], k <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • 0 <= nums[i], k <= 10^9

Hints for Number of Subarrays With AND Value of K

  1. Hint 1

    Fix the right end j and let the left end move left: the AND can only lose bits.

  2. Hint 2

    Each time the AND changes it loses at least one of at most 30 bits, so the subarrays ending at j produce at most 31 distinct AND values.

  3. Hint 3

    Keep, for each j, the list of distinct AND values of subarrays ending at j with how many subarrays give each; build the list for j + 1 from the one for j.

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

  1. Keep a list of pairs (value, count): the distinct ANDs of subarrays ending at the previous index, ordered by start position.
  2. For the new element x, replace every value v by v 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.
  3. 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.
  • k may be 0; zeros in nums make 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 total

Java

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