See all coding puzzles and patterns here.

Problem Definition

Given an integer array and an integer $k$, determine if there is a subarray of minimum length 2 whose sum is divisible by $k$.

Examples

Some test cases to verify our solution.

l = [15, 2, 4, 6, 7]
assert subarray_sum(l, 6)
assert not subarray_sum(l, 15)
assert subarray_sum(l, 12)
assert subarray_sum(l, 13)
assert not subarray_sum(l, 22)
assert subarray_sum(l, sum(l))

assert subarray_sum([23, 2, 4, 6, 6], 7)
assert not subarray_sum([1, 0], 2)

Solution

Suppose there's a subarray of the input array nums with an inclusive start $i$ and inclusive end $j$ such that $(\sum_{x=i}^j num_x) \mod\ k = 0$.

If $pref_i$ is the prefix sum up to and including index $i$ ($\sum_{x=0}^i num_x$), then: $$ (\sum_{x=i}^j num_x) = pref_j-pref_{i-1} $$ And therefore: $$ (\sum_{x=i}^j num_x) \mod\ k = 0 \implies (pref_j-pref_{i-1}) \mod k = 0 \implies pref_j \mod k = pref_{i - 1} \mod k $$

However, if we have an element $num_z = 0$, then $pref_z = pref_{z-1} + num_z = pref_{z-1} + 0 = pref_{z-1} \implies pref_z \mod k = pref_{z - 1} \mod k$. To catch this case, we must check that the prior prefix is at least two elements away in order to satisfy the problem's requirements.

Using this property, we'll store all remainders for each index's prefix sum as we traverse the array. If we find an instance where the remainder has been previously encountered and if that remainder was encountered more than one element ago, then we'll return True. If we don't find a matching remainder, then we'll return False. 

def subarray_sum(nums: list[int], k: int) -> bool:
    if len(nums) < 2:
        return False
    rem = 0
    rem_to_first_idx = {0: -1}
    for idx, num in enumerate(nums):
        rem = (num + rem) % k
        if rem in rem_to_first_idx:
            if rem_to_first_idx[rem] < idx - 1:
                return True
        else:
            rem_to_first_idx[rem] = idx
    return False

Complexity

Let $n = $ len(nums).

Since we're traversing the nums array once, the runtime complexity should be $\Theta(n)$.

Auxiliary space complexity should be $O(k)$ since in the worst case, we might store up to $k$ items in the rem_to_first_idx mapping.