Counting Contiguous Fragments with Given Arithmetic Mean – A Java Coding Challenge

Computer Science Vectors by Vecteezy

Arithmetic Mean problem was recently asked in a Core Java Professionals interview for Synechron Technologies in Bangalore. Let’s dive into the problem statement and explore a solution in Java.

Arithmetic Mean Problem Statement

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.

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

1. 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.
   
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.
   
3. 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.

Arithmetic Mean Solution in Java

Here’s a Java solution to the problem:

class Solution {
    public int solution(int[] A, int S) {
        int N = A.length;
        int result = 0;
        int[] prefixSum = new int[N + 1]; // Compute prefix sum array

        // Compute prefix sum
        for (int i = 1; i <= N; i++) {
            prefixSum[i] = prefixSum[i - 1] + A[i - 1];
        }

        // Iterate over all possible fragments
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                int fragmentSum = prefixSum[j + 1] - prefixSum[i];
                int fragmentLength = j - i + 1;
                if (fragmentSum * 1.0 / fragmentLength == S) {
                    result++;
                    if (result > 1000000000) {
                        return 1000000000; // Return maximum allowed value
                    }
                }
            }
        }

        return result;
    }
}

Arithmetic Mean Solution Explanation

1. We first compute the prefix sum array prefixSum for the given array A. The prefix sum array stores the sum of elements from the start of the array up to each index. This will help us compute the sum of any fragment efficiently.
   
2. Then, we iterate over all possible fragments of the array by considering two nested loops. The outer loop i represents the start of the fragment, and the inner loop j represents the end of the fragment.
   
3. For each fragment [i, j], we compute its sum using the prefix sum array as prefixSum[j + 1] - prefixSum[i]. We also compute the length of the fragment as j - i + 1.
   
4. We check if the arithmetic mean (average) of the fragment is equal to the target value S. The arithmetic mean is computed as fragmentSum * 1.0 / fragmentLength (we use 1.0 to perform floating-point division).
   
5. If the arithmetic mean is equal to S, we increment the result counter. We also check if result exceeds 1000000000, and if so, we return 1000000000 as per the problem statement.
   
6. Finally, we return the result, which represents the number of contiguous fragments whose arithmetic means are equal to S.

The time complexity of this solution is O(N^2), where N is the length of the input array A. This is because we iterate over all possible fragments using nested loops. The space complexity is O(N) due to the prefix sum array.

Note that this solution works for small to medium-sized arrays. For larger arrays, you may need to optimize the solution further or consider different approaches to achieve better time and space complexities.

Conclusion

Coding challenges like this one test your problem-solving abilities, algorithm design skills, and implementation prowess. By practicing such problems, you can enhance your coding skills and better prepare for technical interviews and coding competitions. If you enjoyed this problem and solution, stay tuned for more exciting coding challenges and their solutions in future blog posts.

More Programming Questions on Data Structures

https://codetechsummit.com/category/data-structure/

Ref: https://leetcode.com/discuss/interview-question/1230801/count-number-of-subarrays-with-arithmetic-mean-k