<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return the number of <span data-keyword="subarray-nonempty">subarrays</span> of <code>nums</code> where the bitwise <code>AND</code> of the elements of the subarray equals <code>k</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>All subarrays contain only 1&#39;s.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,2], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 1 are: <code>[<u><strong>1</strong></u>,1,2]</code>, <code>[1,<u><strong>1</strong></u>,2]</code>, <code>[<u><strong>1,1</strong></u>,2]</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3], k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 2 are: <code>[1,<b><u>2</u></b>,3]</code>, <code>[1,<u><strong>2,3</strong></u>]</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        # brute force is n^2
        # but we can see that we can do a very similar idea to the brute force solution
        # by looking at what the brute force solution does
        # basically, brute force will check all subarrays starting at an index i
        # and for each of them, if the bitwise and is equal to k, increment a total
        # and if it's less than k, go to the next index i
        # thus, we can see that
        # as soon as the bitwise and is k, then all further subarrays are valid
        # until you hit a number that's missing one of the bits in k
        # so we can store indices of items that are missing bits in k
        # if not missing bits in k, then num & k == k
        # else, num&k < k
        breaker_indices = deque()
        for index in range(len(nums)):
            if nums[index] & k < k:
                breaker_indices.append(index)
        set_breaker_indices = set(breaker_indices)
        breaker_indices.append(len(nums))  # for edge case handling

        # then, sort of brute force?
        # maybe instead, we look for indices of numbers that don't have
        # certain bits
        # assuming this worked, it'd be 32 * n
        # nums_without_bit only stores items that have at least all bits in k
        nums_without_bit = defaultdict(deque)  # each list is sorted
        # should map bit (1, 2, 4, 8, 16, 32, ...) to a list of indices with numbers without that bit
        for index in range(len(nums)):
            if index in set_breaker_indices:
                continue  # doesn't have all of k's bits

            for bit in range(32):  # 10^9 is like 2^30
                b = 1 << bit  # 1, 2, 4, 8, ...
                if nums[index] & b != b:
                    # doesn't have the bit
                    nums_without_bit[b].append(index)

        # find bits that k doesn't have
        k_not_bits = []
        for bit in range(32):
            b = 1 << bit
            if k & b != b:
                # k doesn't have the bit
                k_not_bits.append(b)

        # so now, for each element in the array, try to get rid of all its bits
        ret = 0
        for index in range(len(nums)):
            if index in set_breaker_indices:
                continue  # doesn't have all of k's bits

            # get next breaker index
            while breaker_indices[0] < index:
                breaker_indices.popleft()
            next_breaker_index = breaker_indices[0]
            
            # has at least all of k's bits, maybe more
            if nums[index] == k:
                # then we have a case where all subarrays until the next breaker index
                # are valid subarrays
                # all subarrays from [here, next_breaker_index) are valid
                n_valid = next_breaker_index - index
                ret += n_valid
            else:
                # has more than k's bits
                # so first, reduce to only k's bits
                last_idx = index
                val = nums[index]
                for extra_bit in k_not_bits:
                    # each of the items in nums_without_bit is guaranteed to keep all the bits in k
                    # but get rid of at least the bit that they are in
                    # so we can just keep bitwise anding and use the last index we find

                    if extra_bit & val != extra_bit:
                        # doesn't have the bit, skip
                        continue
                    # has the bit, get the nearest index
                    d = nums_without_bit[extra_bit]
                    while len(d) > 0 and d[0] < index:
                        d.popleft()
                    if len(d) == 0:
                        # can't do anything, so we can't
                        # remove this bit
                        # so no valid subarrays start here
                        break
                    # else, we can remove the bit
                    val &= nums[d[0]]  # remove the bit
                    last_idx = max(last_idx, d[0])  # move last_idx accordingly
                    
                # once we're here, either val==k (successfully reduced) or val !=k
                # if val==k, then make sure to not include invalid subarrays
                # so check to make sure last_idx happens BEFORE a breaker index
                if val == k and next_breaker_index > last_idx:  
                    # if so, follow same logic from above
                    n_valid = next_breaker_index - last_idx
                    ret += n_valid

        return ret


2639