Continuous Subarray Sum

Problem

Given an integer array nums of non-negative values and a positive integer k, decide whether there is a contiguous subarray of length at least 2 whose elements sum to a multiple of k (zero counts as a multiple). Return True or False.

• The array is non-empty and has at most 200,000 elements.
• Elements are non-negative and can be as large as a billion.
• k is a positive integer and may be much larger than any element or than the total sum.

Examples

• nums = [5, 9, 3, 8, 1], k = 7 → True. [5, 9] sums to 14.
• nums = [8, 2, 5], k = 9 → False. The candidate sums 10, 7, and 15 are not multiples of 9.
• nums = [0, 0], k = 4 → True. [0, 0] sums to 0, a multiple of any k, and has length 2.

Hints

1. A subarray sum is a difference of two prefix sums. When is a difference divisible by k?
2. Two numbers have a difference divisible by k exactly when they leave the same remainder modulo k.
3. Store the first index at which each remainder of the running prefix sum appears; a repeat at distance at least 2 is the answer.