We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays With AND Value of K

Number: 3466

Difficulty: Hard

Paid? No

Companies: DE Shaw

Problem Description

Given an array of integers nums and an integer k, return the number of non-empty contiguous subarrays whose bitwise AND of all the elements equals k.

Key Insights

  • The bitwise AND operation is monotonic in the sense that including an extra number can only remove set bits (or leave them unchanged) in the result.
  • When extending a subarray, the cumulative AND will never “gain” bits but only lose them.
  • Instead of evaluating every possible subarray with a nested loop, we can use a dynamic programming approach that reuses previously computed AND values.
  • We maintain, for every index, a mapping (or dictionary) of all distinct AND values obtained from subarrays ending at that index along with their frequency.
  • As we iterate through the array, we update the mapping by taking the previously stored AND values, combining them with the current number, and also starting a new subarray at the current index.

Space and Time Complexity

Time Complexity: O(n * B) where B is the maximum number of distinct bitwise AND outcomes per index (in practice, B is bounded by the word size, making it effectively O(n)). Space Complexity: O(B) for the mapping of AND values at each iteration.

Solution

We iterate over the array while maintaining a dictionary that stores the counts of subarrays ending at the previous index with their computed AND values. For each index:

  1. Create a new mapping for subarrays ending at the current index.
  2. For every key-value pair in the previous mapping (i.e., for every distinct AND value attained so far), compute the new AND value by including the current element.
  3. Also add the current element as a new subarray.
  4. Update the final count if the new mapping contains the value k.
  5. Move to the next index using the new mapping. This approach efficiently computes the desired result by taking advantage of the fact that only a limited number of distinct AND values arise when combining bits.

Code Solutions

# Python solution for the problem

def count_subarrays_with_and(nums, k):
    # Initialize the result counter and dictionary for subarray AND counts
    count = 0
    prev_and_counts = {}
    
    # Iterate through each number in the array
    for num in nums:
        new_and_counts = {}
        # Extend previous subarrays with the current number
        for and_val, freq in prev_and_counts.items():
            new_val = and_val & num
            new_and_counts[new_val] = new_and_counts.get(new_val, 0) + freq
        
        # Start a new subarray with the current number
        new_and_counts[num] = new_and_counts.get(num, 0) + 1
        
        # If k is present, add its frequency to the total count
        if k in new_and_counts:
            count += new_and_counts[k]
        
        # Update the mapping for the next iteration
        prev_and_counts = new_and_counts
    
    return count

# Example usage:
nums = [1, 1, 2]
k = 1
print(count_subarrays_with_and(nums, k))  # Expected output: 3
← Back to All Questions