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

Count of Interesting Subarrays

Number: 2915

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed integer array nums, an integer modulo, and an integer k, your task is to count the number of subarrays that are interesting. A subarray nums[l..r] is considered interesting if the number of indices i in [l, r] where nums[i] % modulo == k, when taken modulo modulo, equals k. Return the total count of such interesting subarrays.

Key Insights

  • Convert the subarray problem into a prefix-sum formulation by turning each element into an indicator: 1 if nums[i] % modulo == k, otherwise 0.
  • Compute a prefix sum over these indicators so that the sum for any subarray [l, r] is prefix[r] - prefix[l-1].
  • The interesting condition becomes (prefix[r] - prefix[l-1]) % modulo == k.
  • Rearranging the modular equation leads to a two-sum problem by matching prefix[r] % modulo with an adjusted value from the prefix sum frequency.
  • Use a hashmap to store frequencies of each prefix sum modulus encountered, and update the result count based on the required counterpart.

Space and Time Complexity

Time Complexity: O(n), where n is the length of nums, because we iterate through the array once. Space Complexity: O(n) in the worst case due to the hashmap storing the frequency of different prefix sum mod values.

Solution

We first transform the array into an indicator array where each element is 1 if it meets the condition (nums[i] % modulo == k) and 0 otherwise. We then compute the prefix sum for these indicator values. For any subarray [l, r], the interesting condition is equivalent to:   (prefix[r] - prefix[l-1]) % modulo == k. This can be rearranged to:   prefix[r] % modulo - prefix[l-1] % modulo ≡ k (mod modulo), and thus:   prefix[l-1] % modulo = (prefix[r] % modulo - k + modulo) % modulo. By maintaining a hashmap to count the frequencies of the prefix mod values, we can efficiently aggregate the count of interesting subarrays as we iterate through the array.

Code Solutions

# Python solution for Count of Interesting Subarrays

def count_interesting_subarrays(nums, modulo, k):
    # Dictionary to store frequency of prefix mod values
    prefix_mod_count = {}
    # Base case: prefix sum of 0 (before any element) has frequency 1
    prefix_mod_count[0] = 1
    
    answer = 0
    prefix_sum = 0
    
    for num in nums:
        # Increment prefix_sum if condition is satisfied
        if num % modulo == k:
            prefix_sum += 1
        current_mod = prefix_sum % modulo
        # Calculate the target prefix mod needed to form an interesting subarray
        target = (current_mod - k + modulo) % modulo
        # Add the count of prefix sums that match target
        answer += prefix_mod_count.get(target, 0)
        # Update the frequency of the current_mod in the dictionary
        prefix_mod_count[current_mod] = prefix_mod_count.get(current_mod, 0) + 1
    
    return answer

# Example usage:
print(count_interesting_subarrays([3, 2, 4], 2, 1))  # Expected output: 3
← Back to All Questions