Number of Subarrays With AND Value of K
HardPrompt
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 <= 1050 <= nums[i], k <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward solution. It involves generating every possible subarray, calculating the bitwise AND of its elements, and checking if this value equals k. We increment a counter for each subarray that satisfies the condition.
Algorithm
- Initialize a counter
countto 0. - Iterate through the array with an outer loop using index
ifrom 0 ton-1to mark the start of a subarray. - Inside the outer loop, initialize a variable
currentAndto-1(which represents a number with all bits set to 1, the identity for the bitwise AND operation). - Start an inner loop with index
jfromiton-1to mark the end of the subarray. - In the inner loop, update
currentAndby performing a bitwise AND with the current elementnums[j]. (currentAnd &= nums[j]) - Check if the
currentAndis equal tok. If it is, increment thecount. - After the loops complete, return
count.
Walkthrough
This approach uses two nested loops to consider every possible subarray. The outer loop fixes the starting index i, and the inner loop iterates from i to the end of the array, defining the ending index j. For each starting index i, we maintain a currentAnd variable that holds the bitwise AND of elements from nums[i] to nums[j]. As we extend the subarray by incrementing j, we update currentAnd by ANDing it with nums[j]. If at any point currentAnd equals k, we've found a valid subarray and increment our total count. The total count can exceed the capacity of a 32-bit integer, so we use a long to store the result.
class Solution { public long countSubarrays(int[] nums, int k) { int n = nums.length; long count = 0; for (int i = 0; i < n; i++) { int currentAnd = -1; // Represents all bits set to 1 for (int j = i; j < n; j++) { currentAnd &= nums[j]; if (currentAnd == k) { count++; } } } return count; }}Complexity
Time
O(N^2), where N is the number of elements in the array. The two nested loops lead to a quadratic runtime.
Space
O(1) extra space, as we only use a few variables to store the count and the running AND value.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, aside from a few variables.
Cons
The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
Solutions
Solution
class Solution {public long countSubarrays(int[] nums, int k) { long ans = 0; Map<Integer, Integer> pre = new HashMap<>(); for (int x : nums) { Map<Integer, Integer> cur = new HashMap<>(); for (var e : pre.entrySet()) { int y = e.getKey(), v = e.getValue(); cur.merge(x & y, v, Integer : : sum); } cur.merge(x, 1, Integer : : sum); ans += cur.getOrDefault(k, 0); pre = cur; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.