Skip to content

3209. Number of Subarrays With AND Value of K 👍

  • Time: $O(n\log\max(\texttt{arr}))$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  // Similar to 1521. Find a Value of a Mysterious Function Closest to Target
  long long countSubarrays(vector<int>& nums, int k) {
    long long ans = 0;
    // the counter of all the values of subarrays that end in the previous
    // number
    unordered_map<int, int> prev;

    for (const int num : nums) {
      unordered_map<int, int> curr{{num, 1}};
      // Extend each subarray that ends in the previous number. Due to
      // monotonicity of the AND operation, the size of `curr` will be at most
      // num.bit_count() + 1.
      for (const auto& [val, freq] : prev)
        curr[val & num] += freq;
      ans += curr.contains(k) ? curr[k] : 0;
      prev = std::move(curr);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  // Similar to 1521. Find a Value of a Mysterious Function Closest to Target
  public long countSubarrays(int[] nums, int k) {
    long ans = 0;
    // the counter of all the values of subarrays that end in the previous
    // number
    Map<Integer, Integer> prev = new HashMap<>();

    for (final int num : nums) {
      Map<Integer, Integer> curr = new HashMap<>() {
        { put(num, 1); }
      };
      // Extend each subarray that ends in the previous number. Due to
      // monotonicity of the AND operation, the size of `curr` will be at most
      // Integer.bitCount(num) + 1.
      for (Map.Entry<Integer, Integer> entry : prev.entrySet()) {
        final int val = entry.getKey();
        final int freq = entry.getValue();
        curr.merge(val & num, freq, Integer::sum);
      }
      ans += curr.getOrDefault(k, 0);
      prev = curr;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  # Similar to 1521. Find a Value of a Mysterious Function Closest to Target
  def countSubarrays(self, nums: list[int], k: int) -> int:
    ans = 0
    # the counter of all the values of subarrays that end in the previous
    # number
    prev = collections.Counter()

    for num in nums:
      # Extend each subarray that ends in the previous number. Due to
      # monotonicity of the AND operation, the size of `curr` will be at most
      # num.bit_count() + 1.
      curr = collections.Counter({num: 1})
      for val, freq in prev.items():
        curr[val & num] += freq
      ans += curr[k]
      prev = curr

    return ans