Problem Informations

• Problem Index: 2845
• Problem Link: Count of Interesting Subarrays
• Topics: Array, Hash Table, Prefix Sum

Problem Description

You are given a 0-indexed integer array nums, an integer modulo, and an integer k.

Your task is to find the count of subarrays that are interesting.

A subarray nums[l..r] is interesting if the following condition holds:

• Let cnt be the number of indices i in the range [l, r] such that nums[i] % modulo == k. Then, cnt % modulo == k.

Return an integer denoting the count of interesting subarrays.

Note: A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [3,2,4], modulo = 2, k = 1
Output: 3
Explanation: In this example the interesting subarrays are: 
The subarray nums[0..0] which is [3]. 
- There is only one index, i = 0, in the range [0, 0] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 1 and cnt % modulo == k.  
The subarray nums[0..1] which is [3,2].
- There is only one index, i = 0, in the range [0, 1] that satisfies nums[i] % modulo == k.  
- Hence, cnt = 1 and cnt % modulo == k.
The subarray nums[0..2] which is [3,2,4]. 
- There is only one index, i = 0, in the range [0, 2] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 1 and cnt % modulo == k. 
It can be shown that there are no other interesting subarrays. So, the answer is 3.

Example 2:

Input: nums = [3,1,9,6], modulo = 3, k = 0
Output: 2
Explanation: In this example the interesting subarrays are: 
The subarray nums[0..3] which is [3,1,9,6]. 
- There are three indices, i = 0, 2, 3, in the range [0, 3] that satisfy nums[i] % modulo == k. 
- Hence, cnt = 3 and cnt % modulo == k. 
The subarray nums[1..1] which is [1]. 
- There is no index, i, in the range [1, 1] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 0 and cnt % modulo == k. 
It can be shown that there are no other interesting subarrays. So, the answer is 2.

Constraints:

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$
• $1 \leq modulo \leq 10^9$
• $0 \leq k < modulo$

Intuition

The problem presents a task of identifying subarrays within a given array of integers that meet a specific condition regarding modular arithmetic. At first glance, one might consider generating all possible subarrays and calculating if they meet the conditions. However, this approach would be computationally expensive due to the combination explosion. Instead, recognizing the problem as one involving prefix sums and modular arithmetic can lead to a more efficient solution. The idea is to leverage prefix sums to dynamically keep track of conditions across the array without recalculating for each possible subarray.

Approach

To solve the problem efficiently, we use the concept of prefix sums combined with modular arithmetic. The main elements of the approach are as follows:

1. Prefix Sum with Modulo: We maintain a prefix_sum which represents the count of numbers modulo the given modulo that are equal to k, up to the current index. By representing this count as a prefix sum, we can efficiently calculate the condition for any subarray ending at the current index.

2. Hash Map for Counting Prefix Occurrences: We use an unordered map mod_map to track how many times each possible value of prefix_sum % modulo has been seen so far. This allows for a quick count of interesting subarrays ending at the current position by checking the number of ways to form a valid subarray.

3. Calculation: For each element in the array:

   • Update prefix_sum by incrementing if the current number modulo equals k.
   • Reduce prefix_sum modulo modulo to ensure it remains within bounds.
   • Check how many preceding times a prefix has resulted in the condition (prefix_sum - k + modulo) % modulo, which allows formation of a subarray which itself has the interesting condition.
   • Store the current prefix_sum occurrence in the map.

4. Iterating through Array: This approach ensures that we consider each number only once, leading to a linear time complexity in terms of the number of elements, since we are leveraging prefix sums and a hash map to efficiently compute results.

This method efficiently tracks and counts interesting subarrays without redundantly recalculating for each subarray, thereby optimizing the time complexity to $O(n)$.

Code

C++

class Solution {
public:
    // Function to count the number of interesting subarrays
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        unordered_map<int, int> mod_map;  // Map to count occurrences of each prefix_sum % modulo
        long long prefix_sum = 0;         // Variable to store the current prefix sum modulo
        long long interesting_count = 0;  // Variable to store the total count of interesting subarrays
        
        mod_map[prefix_sum]++;  // Initialize by incrementing the count of prefix_sum 0

        // Iterate over each number in the nums array
        for (int num : nums) {
            // Update the prefix sum with the condition, and take mod
            prefix_sum = (prefix_sum + (num % modulo == k)) % modulo;

            // Increment the count by the number of previous prefix sums that match the condition
            interesting_count += mod_map[(prefix_sum - k + modulo) % modulo];

            // Record the current prefix sum in the map
            mod_map[prefix_sum]++;
        }

        return interesting_count;  // Return the total count of interesting subarrays
    }
};

Python

class Solution:
    # Function to count the number of interesting subarrays
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        mod_map = defaultdict(int)  # Map to count occurrences of each prefix_sum % modulo
        prefix_sum = 0  # Variable to store the current prefix sum modulo
        interesting_count = 0  # Variable to store the total count of interesting subarrays
        
        mod_map[prefix_sum] += 1  # Initialize by incrementing the count of prefix_sum 0

        # Iterate over each number in the nums array
        for num in nums:
            # Update the prefix sum with the condition, and take mod
            prefix_sum = (prefix_sum + (num % modulo == k)) % modulo

            # Increment the count by the number of previous prefix sums that match the condition
            interesting_count += mod_map[(prefix_sum - k + modulo) % modulo]

            # Record the current prefix sum in the map
            mod_map[prefix_sum] += 1

        return interesting_count  # Return the total count of interesting subarrays

Complexity

• Time complexity: $O(n)$

  The algorithm iterates over each element of the nums array exactly once, performing constant-time operations for each element. Therefore, the time complexity is linear with respect to the size of the input array $n$.

• Space complexity: $O(\min(n, \text{modulo}))$

  The algorithm utilizes an unordered map mod_map to store the counts of prefix sums modulo modulo. In the worst case, the map can have up to $\min(n, \text{modulo})$ unique keys since the prefix sum modulo operation results in values that are within the range $[0, \text{modulo} - 1]$, but it is also constrained by the number of elements $n$. Therefore, the space complexity is $O(\min(n, \text{modulo}))$.