example: scholarship rank - rFronteddu/general_wiki GitHub Wiki

There is a scholarship test on an education platform.

There are n students with roll numbers 1, 2, ..., n who appeared for the test, where the rank secured by the ith student is denoted by rank[i]. Thus, the array rank is a permutation of length n.

Groups can only be formed with students having consecutive roll numbers, in other words, a subarray of the original array. For each value x (1 <= x <= n), find the number of groups that can be formed such that they have a mean rank equal to x.

More formally, given a permutation of length n, find the number of subarrays of the given array having a mean value equal to x, for each x in the range [1, n].

Notes

• The mean value of an array of k elements is defined as the sum of elements divided by k.
• A permutation of length n is a sequence where each number from q to n appears exactly once.
• A subarray of an array is a contiguous section of the array.

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

public class Solution {
    public static long[] countMeanGroups(int[] rank, int n) {
        long[] counts = new long[n];
        long[] prefixSum = new long[n + 1];

        // Calculate prefix sums
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + rank[i];
        }

        // Iterate through all subarrays
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                int length = end - start + 1;
                long sum = prefixSum[end + 1] - prefixSum[start];

                // Calculate mean value
                long mean = sum / length;

                // Check if it's a valid mean and within the range
                if (mean >= 1 && mean <= n && sum % length == 0) {
                    counts[(int) mean - 1]++; // Increment the count for this mean
                }
            }
        }

        return counts;
    }
}