Continuous Subarray Sum
Medium · Arrays & Hashing · Array · Hash Table · Math · Prefix Sum
Problem
You are given an array of non-negative integers nums and a positive integer k.
Return true if some contiguous subarray of length at least two has a sum that is a multiple of k, and false otherwise.
0 is a multiple of every k, so a subarray of two or more elements that sums to zero counts.
Examples
Input: nums = [5,1,4,2], k = 5 Output: true
The subarray [1, 4] has two elements and sums to 5.
Input: nums = [5,3], k = 5 Output: false
The only subarray with two or more elements is [5, 3], and 8 is not a multiple of 5.
Input: nums = [4,0,0], k = 7 Output: true
The subarray [0, 0] sums to 0, a multiple of 7.
Constraints
- 1 <= len(nums) <= 10^5
- 0 <= nums[i] <= 10^9
- 0 <= sum(nums) <= 2^31 - 1
- 1 <= k <= 2^31 - 1
Approaches
- Baseline: every subarray with prefix sums — time O(n²), space O(n)
Follow-up
Keeping the first index matters: it gives the longest stretch for each remainder, so the length check is as easy to pass as possible. The same "equal remainders" trick finds the shortest or the longest such subarray (keep the latest or the first index); those are the use cases below. If nums could be negative, Python's % still gives a remainder in [0, k), but in Java, C++ and Go you must fix negative remainders yourself.
Related problems
Start free on Cariara · Coding problems · System design studio
