Problem Statement :
You are given an array A of N integers.
Emil decided to split A into continuous subarrays so that each integer is contained in exactly one subarray.
The following information is given:
Value of subarray [L,R] = bitcount( IA[L]l & |A[L+1]| & & & 1A[R]1 ) *A[R].
bitcount(x) denotes the number of ones (set bits) in x.
After splitting A into subarrays, the sum of values for each subarray is taken.
Find the maximum sum that Emil can get. Since the answer can be very large return it modulo 10^9+7.
Ans :
def count_bitwise_and_zero(nums: List[int]) -> int:
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:
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
window_bit_counts += Counter(get_set_bit_indices(right_element))
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