Continuous Subarray Sum

Medium· prefix sum + hash map· modular arithmetic

Problem

Decide whether the array has a contiguous subarray of length at least 2 whose sum is a multiple of k. Zero counts as a multiple of k.

Examples

Input: nums = [23,2,4,6,7], k = 6

Output: true

[2,4] sums to 6, which is a multiple of 6.

Input: nums = [23,2,6,4,7], k = 13

Output: false

Constraints

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 1 <= k <= 2^31 - 1

Hints & approach

Hint 1

A subarray sum is a multiple of k when two prefix sums have the same remainder mod k.

Hint 2

Store the first index where each remainder appears.

Hint 3

Seed the map with remainder 0 at index -1 so prefixes starting at 0 are covered.

Approachtry the hints first

Keep a running prefix sum modulo k and a map from remainder to the earliest index where it appeared, seeded with {0: -1}. At index i, if the current remainder was seen at index j, then the subarray j+1..i sums to a multiple of k; return true if i - j >= 2. Only store a remainder the first time it appears, which keeps the earliest index and maximises length. Return false if the scan ends.

Time O(n) · Space O(min(n, k))

← PreviousSubarray Sum Equals K Next →Subarray Sums Divisible by K