Challenge: Stretches That Hit the Target

Lab Java Intermediate 20 points

Count how many stretches of one or more numbers in a row add up to exactly k. Numbers can be negative, so a sliding window won't work. Combine prefix sums with a HashMap: a stretch ending here hits k whenever an earlier running total equals current − k.

Input

Line 1: n k. Line 2: n whole numbers.

Output

The number of stretches.

Example

Input

5 3
1 2 1 2 1

Output

Sample input available Sample output available

Editor

Java

Hints

Keep a running total and a map: running total → how many times it has appeared.

Start the map with 0 → 1, so stretches starting at index 0 are counted.

Solution explanation

Trying every start and end is O(n²). With the map, each number does one lookup and one update: O(n).

Show solution

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        HashMap<Long, Integer> seen = new HashMap<Long, Integer>();
        seen.put(0L, 1);                 // the empty start: running total 0
        long running = 0, count = 0;
        for (int i = 0; i < n; i++) {
            running += sc.nextInt();
            count += seen.getOrDefault(running - k, 0);
            seen.put(running, seen.getOrDefault(running, 0) + 1);
        }
        System.out.println(count);
    }
}

Output

Answer