Subarray Sums Divisible by K

Prefix Sums, problem 5 of 8

Subarray Sums Divisible by K

Medium

LC #974

prefix sumhash mapmodulo

Not attempted yet

Given an integer array nums and an integer k, return how many non-empty, contiguous subarrays have a sum divisible by k. Numbers may be negative.

Example 1

Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7

The seven subarrays are [5], [5, 0], [0], [5, 0, -2, -3], [0, -2, -3], [-2, -3] and the whole array.

Example 2

Input: nums = [5], k = 9
Output: 0

Constraints

  • 1 ≤ len(nums) ≤ 3 · 10⁴
  • -10⁴ ≤ nums[i] ≤ 10⁴
  • 1 ≤ k ≤ 10⁴

Python

Loading draft…

Test results

8 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

2 examples, 6 hidden

Run examples, then submit all tests.