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.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: nums = [1,1,1], k = 1

Output: 6

Explanation:

All subarrays contain only 1's.

Example 2

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8


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

Solution

Method 1 – Sliding Window with Bitwise AND Tracking

Intuition

To find the number of subarrays whose bitwise AND equals k, we can leverage the fact that the AND operation is monotonic (AND-ing more numbers can only keep or reduce set bits). For each position, we can track all possible AND values ending at that position and count how many times k appears.

Approach

We iterate through the array, and for each element, we keep a map (or set) of all possible AND values for subarrays ending at the current index, along with their counts. For each previous AND value, we compute the AND with the current number and update the map. We also start a new subarray at the current index. We sum the counts where the AND value equals k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from collections import Counter
from typing import List

def countSubarrays(nums: List[int], k: int) -> int:
    ans = 0
    prev = Counter()
    for num in nums:
        curr = Counter()
        curr[num] += 1
        for val, cnt in prev.items():
            curr[val & num] += cnt
        ans += curr[k]
        prev = curr
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
#include <unordered_map>
using namespace std;

int countSubarrays(vector<int>& nums, int k) {
    int ans = 0;
    unordered_map<int, int> prev;
    for (int num : nums) {
        unordered_map<int, int> curr;
        curr[num]++;
        for (auto& [val, cnt] : prev) {
            curr[val & num] += cnt;
        }
        ans += curr[k];
        prev = move(curr);
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;

public class Solution {
    public int countSubarrays(int[] nums, int k) {
        int ans = 0;
        Map<Integer, Integer> prev = new HashMap<>();
        for (int num : nums) {
            Map<Integer, Integer> curr = new HashMap<>();
            curr.put(num, curr.getOrDefault(num, 0) + 1);
            for (Map.Entry<Integer, Integer> entry : prev.entrySet()) {
                int val = entry.getKey() & num;
                curr.put(val, curr.getOrDefault(val, 0) + entry.getValue());
            }
            ans += curr.getOrDefault(k, 0);
            prev = curr;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

fun countSubarrays(nums: IntArray, k: Int): Int {
    var ans = 0
    var prev = mutableMapOf<Int, Int>()
    for (num in nums) {
        val curr = mutableMapOf<Int, Int>()
        curr[num] = curr.getOrDefault(num, 0) + 1
        for ((val_, cnt) in prev) {
            val andVal = val_ and num
            curr[andVal] = curr.getOrDefault(andVal, 0) + cnt
        }
        ans += curr.getOrDefault(k, 0)
        prev = curr
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func countSubarrays(nums []int, k int) int {
    ans := 0
    prev := map[int]int{}
    for _, num := range nums {
        curr := map[int]int{}
        curr[num]++
        for val, cnt := range prev {
            curr[val&num] += cnt
        }
        ans += curr[k]
        prev = curr
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

use std::collections::HashMap;

pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i32 {
    let mut ans = 0;
    let mut prev = HashMap::new();
    for &num in &nums {
        let mut curr = HashMap::new();
        *curr.entry(num).or_insert(0) += 1;
        for (&val, &cnt) in prev.iter() {
            *curr.entry(val & num).or_insert(0) += cnt;
        }
        ans += *curr.get(&k).unwrap_or(&0);
        prev = curr;
    }
    ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function countSubarrays(nums: number[], k: number): number {
    let ans = 0;
    let prev = new Map<number, number>();
    for (const num of nums) {
        const curr = new Map<number, number>();
        curr.set(num, (curr.get(num) || 0) + 1);
        for (const [val, cnt] of prev.entries()) {
            const andVal = val & num;
            curr.set(andVal, (curr.get(andVal) || 0) + cnt);
        }
        ans += curr.get(k) || 0;
        prev = curr;
    }
    return ans;
}

Complexity

  • ⏰ Time complexity: O(n * log(maxA)) where n is the length of nums and maxA is the maximum value in nums (since the number of unique AND values per position is at most log(maxA)).
  • 🧺 Space complexity: O(log(maxA)) for the map of AND values per position.