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.
C++
// CPP program to find floor value// of mean in range l to r#include <bits/stdc++.h>using namespace std;// To find mean of range in l to rint 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 = floor(sum / count); // Returns mean of array // in range l to r return mean;}// Driver program to test findMean()int main(){ int arr[] = { 1, 2, 3, 4, 5 }; cout << findMean(arr, 0, 2) << endl; cout << findMean(arr, 1, 3) << endl; cout << findMean(arr, 0, 4) << endl; return 0;} |
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).
C++
// CPP program to find floor value// of mean in range l to r#include <bits/stdc++.h>#define MAX 1000005using namespace std;int prefixSum[MAX];// To calculate prefixSum of arrayvoid 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 rint findMean(int l, int r){ if (l == 0) return 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 floor((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1));}// Driver program to test above functionsint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); calculatePrefixSum(arr, n); cout << findMean(0, 2) << endl; cout << findMean(1, 3) << endl; cout << findMean(0, 4) << endl; return 0;} |
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!