Given an array of n integers. You are given q queries. Write a program to print the floor value of mean in range l to r for each query in a new line.
Examples :
Input : arr[] = {1, 2, 3, 4, 5}
q = 3
0 2
1 3
0 4
Output : 2
3
3
Here for 0 to 2 (1 + 2 + 3) / 3 = 2
Input : arr[] = {6, 7, 8, 10}
q = 2
0 3
1 2
Output : 7
7
Naive Approach: We can run loop for each query l to r and find sum and number of elements in range. After this we can print floor of mean for each query.
Java
// Java program to find floor value// of mean in range l to rpublic class Main { // To find mean of range in l to r static int findMean(int arr[], int l, int r) { // Both sum and count are // initialize to 0 int sum = 0, count = 0; // To calculate sum and number // of elements in range l to r for (int i = l; i <= r; i++) { sum += arr[i]; count++; } // Calculate floor value of mean int mean = (int)Math.floor(sum / count); // Returns mean of array // in range l to r return mean; } // Driver program to test findMean() public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5 }; System.out.println(findMean(arr, 0, 2)); System.out.println(findMean(arr, 1, 3)); System.out.println(findMean(arr, 0, 4)); }} |
Output :
2 3 3
Time complexity: O(n*q) where q is the number of queries and n is the size of the array. Here in the above code q is 3 as the findMean function is used 3 times.
Auxiliary Space: O(1)
Efficient Approach: We can find sum of numbers using numbers using prefix sum. The prefixSum[i] denotes the sum of first i elements. So sum of numbers in range l to r will be prefixSum[r] – prefixSum[l-1]. Number of elements in range l to r will be r – l + 1. So we can now print mean of range l to r in O(1).
Java
// Java program to find floor value// of mean in range l to rpublic class Main {public static final int MAX = 1000005; static int prefixSum[] = new int[MAX]; // To calculate prefixSum of array static void calculatePrefixSum(int arr[], int n) { // Calculate prefix sum of array prefixSum[0] = arr[0]; for (int i = 1; i < n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i]; } // To return floor of mean // in range l to r static int findMean(int l, int r) { if (l == 0) return (int)Math.floor(prefixSum[r] / (r + 1)); // Sum of elements in range l to // r is prefixSum[r] - prefixSum[l-1] // Number of elements in range // l to r is r - l + 1 return (int)Math.floor((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1)); } // Driver program to test above functions public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5 }; int n = arr.length; calculatePrefixSum(arr, n); System.out.println(findMean(1, 2)); System.out.println(findMean(1, 3)); System.out.println(findMean(1, 4)); }} |
Output:
2 3 3
Time complexity: O(n+q) where q is the number of queries and n is the size of the array. Here in the above code q is 3 as the findMean function is used 3 times.
Auxiliary Space: O(k) where k=1000005.
Please refer complete article on Mean of range in array for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!