You are given an integer array nums sorted in non-descending order and a positive integer k.

A subarray of nums (a contiguous, non-empty sequence of elements) is called good if the sum of its elements is divisible by k.

Your task is to return the number of distinct good subarrays of nums.

The key twist here is the word distinct: two subarrays are considered the same if their sequences of values are identical, even if they occupy different positions in the array. In other words, duplicates by value must be counted only once.

For example, in the array [1, 1, 1], although there are 6 possible subarray positions, there are only 3 distinct subarrays by value:

• [1]
• [1, 1]
• [1, 1, 1]

So when counting good subarrays, you must be careful not to count the same value sequence more than once.

Two important properties shape the problem:

1. Divisibility condition — A subarray with sum s is good if and only if s % k == 0. Using prefix sums, a subarray nums[i+1..j] is good exactly when prefix[j] % k == prefix[i] % k.
2. Sorted input — Because nums is sorted in non-descending order, any two subarrays with identical value sequences must consist of a run of equal elements. This means duplicate subarrays can only arise inside maximal blocks of repeated values, e.g., a block like [3, 3, 3, 3]. Within a block of length m, a subarray of length h (all elements equal to v) appears m - h + 1 times positionally, but should only be counted once if its sum h * v is divisible by k.

Therefore, the overall answer can be obtained by:

• First counting all good subarrays by position (the classic prefix-sum-modulo counting technique with a hash map cnt, starting with cnt[0] = 1).
• Then subtracting the over-counted duplicates: for every maximal run of equal values of length m, and for each subarray length h from 1 to m, if (h * v) % k == 0, that value sequence was counted m - h + 1 times but should count only once, so we subtract the extra m - h occurrences.

The final result is the number of distinct good subarrays.

If the problem only asked for the number of subarrays whose sum is divisible by k, it would be a classic prefix-sum problem: a subarray nums[i+1..j] has a sum divisible by k exactly when prefix[j] % k == prefix[i] % k. So we can scan the array once, keep a running sum modulo k, and use a hash map to count how many earlier prefixes share the same remainder — each match contributes one good subarray. This counts every good subarray by position.

The real difficulty is the word distinct: identical value sequences appearing at different positions must be counted only once. Counting distinct subarrays in a general array is hard (it usually needs suffix structures), so we should ask: why does the problem tell us the array is sorted?

Here is the key observation. Suppose two different positions hold the same value sequence, say nums[i..i+L-1] and nums[j..j+L-1] with i < j. The two windows overlap or are adjacent in value terms: the first element of the second copy, nums[j], must equal nums[i], and since the array is non-descending, every element between index i and j + L - 1 is squeezed between equal values — so they are all equal. In other words, in a sorted array, duplicate subarrays can only occur inside a maximal run of identical elements.

This turns a hard "count distinct" problem into a simple correction step:

• Within a run of m equal values v, a subarray of length h (for 1 <= h <= m) appears m - h + 1 times positionally, but it represents just one distinct value sequence.
• Outside such runs, every positional subarray is automatically distinct, so the prefix-sum count is already correct for them.

So the plan emerges naturally:

1. Count all good subarrays by position using the prefix-sum-modulo trick — this over-counts duplicates.
2. Walk through each maximal run of equal values of length m. For each length h where the sum h * v is divisible by k, that sequence was counted m - h + 1 times but should count once, so subtract the surplus m - h.

Two perspectives confirm this is efficient:

• The prefix-sum pass is O(n).
• The correction loop looks nested, but the inner loop over h runs m times per run, and the runs partition the array, so the total work is also O(n).

By combining the classic counting technique with the structural guarantee provided by sortedness, we get an exact count of distinct good subarrays without ever needing heavyweight string/sequence deduplication machinery.

Pattern Learn more about Prefix Sum patterns.

The solution runs in two phases: count everything by position, then subtract the duplicates that only sorted arrays can produce inside runs of equal values.

Phase 1: Count all good subarrays by position (prefix sum + hash map)

We use a Counter named cnt to record how many prefixes have produced each remainder modulo k. It is initialized as cnt = Counter({0: 1}) — the empty prefix has sum 0, which allows subarrays starting at index 0 to be counted correctly.

cnt = Counter({0: 1})
ans = s = 0
for x in nums:
    s = (s + x) % k
    ans += cnt[s]
    cnt[s] += 1

For each element x:

• Update the running prefix sum modulo k: s = (s + x) % k.
• Every earlier prefix with the same remainder s pairs with the current position to form a subarray whose sum is divisible by k, so we add cnt[s] to the answer.
• Record the current remainder: cnt[s] += 1.

After this loop, ans equals the number of good subarrays counted positionally — duplicates included.

Phase 2: Subtract over-counted duplicates inside equal-value runs

Because nums is sorted, identical value sequences can only appear inside a maximal block of repeated elements. We scan the array with a two-pointer pattern to locate each such block:

n = len(nums)
i = 0
while i < n:
    j = i + 1
    while j < n and nums[j] == nums[i]:
        j += 1
    m = j - i
    for h in range(1, m + 1):
        if (h * nums[i]) % k == 0:
            ans -= m - h
    i = j

• The inner while advances j past all elements equal to nums[i], so m = j - i is the length of the current run of the value v = nums[i].
• For each possible subarray length h inside this run (1 <= h <= m), the subarray consists of h copies of v, with sum h * v. If (h * v) % k == 0, this sequence is good — but Phase 1 counted it m - h + 1 times (once for each starting position inside the run), while it should be counted exactly once. So we subtract the surplus m - h.
• Finally, i = j jumps to the start of the next run.

Note that subarrays which are not fully contained inside a single run are guaranteed to be distinct by value (the sortedness argument from the intuition), so no correction is needed for them.

Why the result is exact

• Phase 1 counts every good (start, end) pair: this equals the distinct count plus the duplicate surplus.
• Phase 2 removes precisely that surplus, run by run, length by length.

Complexity Analysis

• Time complexity: O(n). The prefix-sum pass visits each element once. In Phase 2, the pointers i and j only move forward, and the inner for h loop performs m iterations per run; since the runs partition the array, the total across all runs is n iterations.
• Space complexity: O(min(n, k)) for the hash map cnt, since remainders modulo k take at most k distinct values, and at most n + 1 prefixes are recorded.