dsa · medium

Continuous Subarray Sum

You are given an integer array nums and an integer k. Return true if there is a subarray of length at least 2 whose elements sum to a multiple of k, false otherwise. A multiple of k includes 0 itself.

Arguments

• nums — the input array
• k — the divisor

Example

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

The subarray [2,4] sums to 6, which is a multiple of 6 → true.

nums = [23,2,6,4,7], k = 13 → no subarray of length 2 or more sums to a multiple of 13 → false.

Constraints

1 <= nums.length <= 10^5 0 <= nums[i] <= 10^9 0 <= k <= 10^9 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

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

Expected:
true

Example 2

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

Expected:
true

Example 3

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

Expected:
false

Open in the Dojo editor