#### Count contiguous subarray of given target Average

Question::

You are given an array A of N integers and an integer S. Your task is to compute how many ways one can choose a contiguous fragment of A that has an arithmetic mean equal to S. The arithmetic mean (average) of a fragment is the sum of the elements of the fragment divided by its length. For example, the arithmetic mean of [1, 4, 4, 5] is 14/4 = 3.5.

Write a function:

``````class Solution { public int solution(int[] A, int S); }
``````

which returns the number of contiguous fragments of A whose arithmetic means are equal to S.

If the result is greater than 1,000,000,000, your function should return 1,000,000,000.

Examples:

Given A = [2, 1, 3] and S = 2, your function should return 3, since the arithmetic means of fragments [2], [1, 3] and [2, 1, 3] are equal to 2.
Given A = [0, 4, 3, -1] and S = 2, your function should return 2, since fragments [0, 4] and [4, 3, -1] have an arithmetic mean equal to 2.
Given A = [2, 1, 4] and S = 3, your function should return 0, since there exist no contiguous fragments whose arithmetic mean is equal to 3.
Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

S is an integer within the range [-1,000,000,000..1,000,000,000];

each element of array A is an integer within the range [-1,000,000,000..1,000,000,000].

Solutions I tried in java 8::

1. Brute force method I tried, is passing for base cases but giving runtime errors at submission.
``````
public class Solution {
public int solution(int[] A, int S) {
int n = A.length;
int count = 0;

for (int start = 0; start < n; start++) {
long sum = 0;
for (int end = start; end < n; end++) {
sum += A[end];
int length = end - start + 1;
if (sum == (long) S * length) {
count++;
}
}
}

// Return 1,000,000,000 if the count exceeds this value
if (count > 1_000_000_000) {
return 1_000_000_000;
}

return count;
}
``````
1. All methods I tried to optimise to O(n) time complexity but it is failing for only 1 test base case and don’t know for other test cases and that test case is
``````Example test:   [[2, 1, 3], 2]
WRONG ANSWER (got 2 expected 3)
``````

Code1:

``````
import java.util.*;

class Solution {
public int solution(int[] A, int S) {
int N = A.length;
int count = 0;
long sum = 0;
int left = 0, right = 0;

while (right < N) {
sum += A[right];

while (sum > S * (right - left + 1)) {
sum -= A[left];
left++;
}

if (sum == S * (right - left + 1)) {
count++;
}

right++;
}

return Math.min(count, 1000000000);
}
}

``````

Code2:

``````
import java.util.HashMap;
import java.util.Map;

public class Solution {
public int solution(int[] A, int S) {
int n = A.length;
long count = 0;
long sum = 0;

Map<Long, Integer> prefixSums = new HashMap<>();
prefixSums.put(0L, 1);

for (int i = 0; i < n; i++) {
sum += A[i];

long neededSum = sum - (long) S * (i + 1);

if (prefixSums.containsKey(neededSum)) {
count += prefixSums.get(neededSum);
}

prefixSums.put(sum, prefixSums.getOrDefault(sum, 0) + 1);

if (count > 1_000_000_000) {
return 1_000_000_000;
}
}
return (int) count;
}
``````