Number of subarrays with and value of k

Array Binary Search Bit Manipulation Segment Tree

35.1% acceptance

Feb 25, 2026

170

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i64 {
    let mut result = 0i64;
    // prev: list of (and_value, count) for all subarrays ending at previous position
    let mut prev: Vec<(i32, i64)> = Vec::new();
    for &x in &nums {
      let mut curr: Vec<(i32, i64)> = vec![(x, 1)];
      for &(val, cnt) in &prev {
        let new_val = val & x;
        if curr.last().unwrap().0 == new_val {
          curr.last_mut().unwrap().1 += cnt;
        } else {
          curr.push((new_val, cnt));
        }
      }
      for &(val, cnt) in &curr {
        if val == k {
          result += cnt;
        }
      }
      prev = curr;
    }
    result
  }
}