PythonMediumHashing20 min

Count subarrays with a target sum

Values may be negative or zero. Count all index ranges separately, even when they contain identical values. Interviewers use this problem to assess count previous prefix sums rather than using a positive-only sliding window.

Input

First line: n and target. Second line: n integers.

Output

Print the result on one line; print an empty line for an empty string.

Constraints

0 <= n <= 100000; -10^9 <= values and target <= 10^9.

Example

Input

3 2
1 1 1

Output

Example 2 input

3 -3
-1 -2 -3

Output

Negative targets and negative numbers are supported.

Public test cases (2)

Input
```
3 2
1 1 1
```
Expected output
```
2
```
Input
```
5 0
1 -1 0 1 -1
```
Expected output
```
7
```

Hints (2)

Identify the state needed to avoid repeated work.
Count previous prefix sums rather than using a positive-only sliding window.

Target complexity: time O(n) expected · space O(n)

Your solution

import sys


def solve_subarray_sum_count(a, target):
    # your code
    return 0


if __name__ == "__main__":
    data = sys.stdin.read()
    tokens = list(map(int, data.split()))
    n, target = tokens[:2]
    a = tokens[2:2 + n]
    result = solve_subarray_sum_count(a, target)
    print(result)

Standard input

Checking runner availability…

Reference solution

Check whether a number is prime · Easy
Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the missing number from zero through n · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy

All Python programs

Count subarrays with a target sum

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs