Count Subarrays Summing to K

MediumArrayPrefix-SumHashingCounting5 hidden tests

Count the number of contiguous subarrays whose elements sum to exactly k. Values may be negative.

Input format

Line 1: two integers n and k. Line 2: n space-separated integers (present whenever n >= 1).

One line: the number of contiguous subarrays whose sum is k.

Example 1

Input

4 2
1 1 1 1

Expected

Explanation

The subarrays [1,1] at positions (0,1),(1,2),(2,3) each sum to 2, giving 3.

Example 2

Input

3 3
1 2 3

Expected

Explanation

[1,2] and [3] both sum to 3, giving 2.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.