All problems

Continuous Subarray Sum

Medium · prefix sum

You are given a list nums of non-negative integers and a positive integer k.

A run is a block of one or more neighbouring numbers in the list. Its total is the sum of the numbers in the block.

Return true if some run of at least two numbers has a total that is a multiple of k, and false otherwise. A total of 0 counts as a multiple of k.

Examples

Example 1

Input: nums = [3, 4, 5], k = 3

Output: true

The run [4, 5] has total 9, which is 3 times 3.

Example 2

Input: nums = [5, 2, 9], k = 5

Output: false

The single number 5 is a multiple of 5, but a run needs two numbers. The totals of the two-number and three-number runs are 7, 11 and 16.

Example 3

Input: nums = [0, 0], k = 7

Output: true

The run [0, 0] has total 0, which counts as a multiple of 7.

Constraints