**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::**

- 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;
}
```

- 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;
}
```

Please help me to find the fault in logic or code where it is calculating wrongly.

I also tried to print all the combinations of subarray but wasn’t getting the correct result on that as well.