Continuous Subarray Sum

Medium

Problem

Return true if the array has a contiguous subarray of length at least 2 whose sum is a multiple of k (0 counts as a multiple).

Example 1

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

[2, 4] sums to 6.

Example 2

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

Test cases

Case 1

Input:    [23,2,4,6,7], 6
Expected: true

Case 2

Input:    [23,2,6,4,7], 13
Expected: false

Case 3

Input:    [23,2,6,4,7], 6
Expected: true

Case 4

Input:    [5,0,0], 3
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Prefix remainders

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

Two prefixes with the same remainder mod k bound a subarray whose sum is a multiple of k. Store the first index of each remainder; require length ≥ 2.

function checkSubarraySum(nums, k) {
const first = new Map([[0, -1]]); // remainder -> earliest index
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum = (sum + nums[i]) % k;
if (first.has(sum)) {
if (i - first.get(sum) >= 2) return true;
} else first.set(sum, i);
}
return false;
}