Suppose we have a list of numbers
[7,2,9,8,6,12,109,28,14,19]
I want to find a efficient way to count the all sub-list of this list which will have bitwise and equal to zero
like:
[2,5] # 2&5 = 0
[9,5,7,2] # 9&5&7&2 = 0
Let me know if anyone know how to do it most efficiently
You can do this in O(n) time using a sliding window.
If we know that a subarray of A on indices [L, R] has an & of zero, then we know that all larger subarrays ([L, R + 1], [L, R + 2], [L, R + 3], ...) will also have an & of zero due to monotonicity of & under inclusion.
For example, computing the partial & products of an array from the left:
Array (Base 10): [ 7, 3, 10, 5]
Array (Binary) : [111, 11, 1010, 101]
Partial &s : [111, 11, 10, 0]
We'll iterate over the right end of our sliding window, while storing the smallest left end (i.e. the largest window) such that A[left, left + 1, ... right] has a nonzero bitwise &. Note that this left end can only ever increase as the right end increases.
To update our window, we'll need to
& of our window with A[right] (easy)& of A[left] from our window (hard)To do removals efficiently, we'll instead track the count of set-bits for all elements in our window at each bit position. This lets us add and remove elements from our window, and test whether the & of our window is zero by testing whether each set bit position has a count less than the length of the window.
Here's a walkthrough of the maximal nonzero windows on an example array:
Base 10:
A = [7, 2, 9, 8, 6, 12, 109, 28, 14, 19]
Binary:
111, 10, 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011
Maximal nonzero [windows] at each right endpoint:
--------------------------------------------------------------
[111], 10, 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011
^ ^
left = 0, right = 0, size = 1
--------------------------------------------------------------
[111, 10], 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011
^ ^
left = 0, right = 1, size = 2
--------------------------------------------------------------
111, 10, [1001], 1000, 110, 1100, 1101101, 11100, 1110, 10011
^ ^
left = 2, right = 2, size = 1
--------------------------------------------------------------
111, 10, [1001, 1000], 110, 1100, 1101101, 11100, 1110, 10011
^ ^
left = 2, right = 3, size = 2
--------------------------------------------------------------
111, 10, 1001, 1000, [110], 1100, 1101101, 11100, 1110, 10011
^ ^
left = 4, right = 4, size = 1
--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100], 1101101, 11100, 1110, 10011
^ ^
left = 4, right = 5, size = 2
--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101], 11100, 1110, 10011
^ ^
left = 4, right = 6, size = 3
--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101, 11100], 1110, 10011
^ ^
left = 4, right = 7, size = 4
--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101, 11100, 1110], 10011
^ ^
left = 4, right = 8, size = 5
--------------------------------------------------------------
111, 10, 1001, 1000, 110, 1100, 1101101, 11100, [1110, 10011]
^ ^
left = 8, right = 9, size = 2
Here, the sum of nonzero-& window sizes is 23. As a length 10 array has 55 possible subarrays, the answer is 55 - 23 = 32 bitwise-&-zero subarrays.
Python code:
def count_bitwise_and_zero(nums: List[int]) -> int:
"""Count nonempty subarrays with & of elements equal to 0.
Given a list on nonnegative integers,
returns the number of contiguous, nonempty subarrays for which the
bitwise and of all elements in the subarray are equal to 0.
Runs in linear time on fixed-width integers.
"""
def get_set_bit_indices(x: int) -> List[int]:
"""Return indices of set bits in x"""
pow_2 = 1
exponent = 0
set_bits = []
while pow_2 <= x:
if pow_2 & x != 0:
set_bits.append(exponent)
exponent += 1
pow_2 *= 2
return set_bits
def is_bitwise_and_zero(window_length: int, bit_counts: Dict[int, int]) -> bool:
"""Given bit counts for a window of an array, return whether the
window's elements have bitwise AND equal to zero."""
return all(value < window_length for value in bit_counts.values())
n = len(nums)
total_subarray_count = n * (n + 1) // 2
nonzero_subarray_count = 0
window_bit_counts = Counter()
"""At every iteration start, [left_idx, right_idx] is the longest subarray
ending at right_idx whose bitwise AND is nonzero."""
left_idx = 0
for right_idx, right_element in enumerate(nums):
if right_element == 0:
window_bit_counts.clear()
left_idx = right_idx + 1
continue
# Expand window to include right
window_bit_counts += Counter(get_set_bit_indices(right_element))
# Shrink window until AND is nonzero
while (left_idx < right_idx
and is_bitwise_and_zero(right_idx - left_idx + 1, window_bit_counts)):
window_bit_counts -= Counter(get_set_bit_indices(nums[left_idx]))
left_idx += 1
nonzero_subarray_count += (right_idx - left_idx + 1)
return total_subarray_count - nonzero_subarray_count
Example usage:
count_bitwise_and_zero([7, 2, 9, 8, 6, 12, 109, 28, 14, 19])
>>> 32
N.B. There's an assumption that the maximum bit-width of the integers is constant. To get a linear-time solution when integers can be arbitrarily large, you'll need to keep a meta-counter, which tracks counts of counts of set bits.
As an exercise, you can try to generalize to the problem of bitwise & equal to some target t which may be greater than zero; it takes a bit more work.