Algorithms
Medium
2845
2915
Count of Interesting Subarrays
count-of-interesting-subarrays
"""
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 <= nums.length <= 105
 * 1 <= nums[i] <= 109
 * 1 <= modulo <= 109
 * 0 <= k < modulo
"""
class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        
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 <= nums.length <= 105
 * 1 <= nums[i] <= 109
 * 1 <= modulo <= 109
 * 0 <= k < modulo


Please complete the code below to solve above prblem:
```python
class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [3,2,4], "modulo": 2, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [3,1,9,6], "modulo": 3, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 2

test_input = { "nums": [11,12,21,31], "modulo": 10, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 5

test_input = { "nums": [2,4], "modulo": 7, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [2,7], "modulo": 7, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [2,45], "modulo": 13, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [3,3], "modulo": 5, "k": 3 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [3,4], "modulo": 8, "k": 3 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [4,5], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [5,1], "modulo": 6, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 2

test_input = { "nums": [7,2], "modulo": 7, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [7,4], "modulo": 7, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [8,8], "modulo": 4, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [9,2], "modulo": 2, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [18,43], "modulo": 3, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [19,67], "modulo": 47, "k": 19 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [20,8], "modulo": 41, "k": 8 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [26,5], "modulo": 21, "k": 5 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [81,36], "modulo": 4, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [2,1,5], "modulo": 9, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [2,2,5], "modulo": 3, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 2

test_input = { "nums": [2,2,5], "modulo": 4, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 2

test_input = { "nums": [2,3,2], "modulo": 6, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [3,2,5], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [5,1,6], "modulo": 2, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [5,2,8], "modulo": 2, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [6,5,6], "modulo": 6, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [7,1,2], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [7,2,9], "modulo": 4, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [7,5,6], "modulo": 4, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [9,1,6], "modulo": 7, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [40,1,24], "modulo": 41, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [48,36,27], "modulo": 9, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [1,9,6,1], "modulo": 2, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [2,2,1,2], "modulo": 3, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [3,5,4,2], "modulo": 5, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [4,18,38,15], "modulo": 21, "k": 4 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [6,6,1,4], "modulo": 7, "k": 6 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [7,5,2,1], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 10

test_input = { "nums": [7,5,3,4], "modulo": 3, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [8,6,5,6], "modulo": 3, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 2

test_input = { "nums": [8,7,3,2], "modulo": 6, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 1

test_input = { "nums": [9,2,2,6], "modulo": 7, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [9,7,4,1], "modulo": 2, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [9,7,8,9], "modulo": 5, "k": 4 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [9,48,32,11], "modulo": 2, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [53,44,40,37], "modulo": 2, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [91,5,60,93], "modulo": 59, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [2,1,1,3,5], "modulo": 4, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [2,2,5,4,3], "modulo": 5, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [2,2,5,6,1], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 15

test_input = { "nums": [2,6,2,3,1], "modulo": 9, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [2,7,4,8,5], "modulo": 2, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 7

test_input = { "nums": [4,2,1,8,8], "modulo": 3, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [4,2,8,8,2], "modulo": 9, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 2

test_input = { "nums": [5,6,3,9,3], "modulo": 9, "k": 3 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [6,7,1,9,2], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 15

test_input = { "nums": [6,9,5,1,6], "modulo": 5, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 7

test_input = { "nums": [7,3,6,2,6], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 15

test_input = { "nums": [7,7,9,5,8], "modulo": 4, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 5

test_input = { "nums": [7,9,1,3,2], "modulo": 8, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 5

test_input = { "nums": [8,6,9,4,4], "modulo": 9, "k": 4 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [8,8,6,8,9], "modulo": 9, "k": 8 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [9,7,8,7,8], "modulo": 7, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 3

test_input = { "nums": [26,9,14,4,24], "modulo": 26, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 10

test_input = { "nums": [31,30,24,34,20], "modulo": 22, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [39,41,6,30,38], "modulo": 43, "k": 6 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [1,2,7,1,6,6], "modulo": 5, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 8

test_input = { "nums": [1,6,2,1,9,7], "modulo": 3, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 11

test_input = { "nums": [1,7,8,2,5,9], "modulo": 7, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 10

test_input = { "nums": [2,4,6,6,5,1], "modulo": 8, "k": 6 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [2,8,2,9,2,8], "modulo": 5, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [2,9,1,6,5,7], "modulo": 7, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 5

test_input = { "nums": [2,9,1,6,6,7], "modulo": 9, "k": 6 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [2,9,6,8,8,3], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 21

test_input = { "nums": [4,8,4,3,7,5], "modulo": 4, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [4,9,4,9,7,7], "modulo": 9, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 5

test_input = { "nums": [5,3,7,9,8,7], "modulo": 3, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 5

test_input = { "nums": [7,1,6,1,7,2], "modulo": 6, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 7

test_input = { "nums": [7,3,1,9,1,3], "modulo": 5, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 10

test_input = { "nums": [7,4,9,8,3,4], "modulo": 1, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 21

test_input = { "nums": [7,5,1,7,7,7], "modulo": 8, "k": 7 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [8,4,5,6,7,4], "modulo": 4, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [8,7,3,8,4,8], "modulo": 8, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [8,7,5,5,2,1], "modulo": 5, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 6

test_input = { "nums": [8,18,36,50,12,37], "modulo": 18, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 7

test_input = { "nums": [9,9,6,7,2,3], "modulo": 5, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 8

test_input = { "nums": [16,1,33,39,15,1], "modulo": 30, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 12

test_input = { "nums": [17,25,9,20,41,26], "modulo": 38, "k": 3 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [21,26,39,21,31,49], "modulo": 22, "k": 21 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [37,44,17,22,50,15], "modulo": 6, "k": 2 }
assert my_solution.countInterestingSubarrays(**test_input) == 4

test_input = { "nums": [40,10,31,40,30,32], "modulo": 50, "k": 40 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [40,22,22,35,2,16], "modulo": 24, "k": 16 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [98,23,66,13,70,34], "modulo": 74, "k": 13 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [1,1,4,8,3,2,7], "modulo": 9, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 7

test_input = { "nums": [1,8,6,3,2,8,8], "modulo": 2, "k": 0 }
assert my_solution.countInterestingSubarrays(**test_input) == 13

test_input = { "nums": [1,9,2,1,5,4,8], "modulo": 4, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 8

test_input = { "nums": [4,6,8,3,4,3,4], "modulo": 7, "k": 4 }
assert my_solution.countInterestingSubarrays(**test_input) == 0

test_input = { "nums": [5,4,5,8,9,1,9], "modulo": 4, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 11

test_input = { "nums": [5,4,6,1,3,2,7], "modulo": 9, "k": 1 }
assert my_solution.countInterestingSubarrays(**test_input) == 16