Interesting Experiences: Count Subarrays Meeting a Scoring Threshold

Question

## Problem

You are given an array of integers `nums` and an integer `k`. A subarray is "interesting" if the sum of its elements is divisible by `k`. Count the number of interesting subarrays.

```python
def count_interesting_subarrays(nums: list[int], k: int) -> int:
    pass
```

**Example:**
```
Input:  nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7

All subarrays with sum divisible by 5:
  [4,5,0,-2,-3,1], [5], [5,0,-2,-3], [0,-2,-3], [-2,-3], etc.
```

## Approach

Use prefix sums mod `k`. If `prefix[i] mod k == prefix[j] mod k`, then `sum(i+1..j)` is divisible by `k`. Track counts of each remainder seen so far.

```python
from collections import defaultdict

def count_interesting_subarrays(nums, k):
    count = defaultdict(int)
    count[0] = 1
    prefix = 0
    result = 0
    for n in nums:
        prefix = (prefix + n) % k
        result += count[prefix]
        count[prefix] += 1
    return result
```

## Follow-ups

1. How does handling negative numbers affect the modulo operation in Python vs. C++?
2. What if you need the longest interesting subarray, not the count?
3. Extend to 2D: count submatrices whose sum is divisible by k.
4. What is the time and space complexity of your solution?

Interesting Experiences: Count Subarrays Meeting a Scoring Threshold

Question Details

Full Details

Topics

More from Airbnb