3209. Number of Subarrays With AND Value of K LeetCode Solution
In this guide, you will get 3209. Number of Subarrays With AND Value of K LeetCode Solution with the best time and space complexity. The solution to Number of Subarrays With AND Value of K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Subarrays With AND Value of K
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.
Example 1:
Input: nums = [1,1,1], k = 1
Output: 6
Explanation:
All subarrays contain only 1’s.
Example 2:
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:
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 <= 105
0 <= nums[i], k <= 109
Complexity Analysis
Time Complexity: O(n\log\max(\texttt{arr}))
Space Complexity: O(n)
3209. Number of Subarrays With AND Value of K LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
3209. Number of Subarrays With AND Value of K LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
3209. Number of Subarrays With AND Value of K LeetCode Solution in Python
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 # code by PROGIEZ
