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.
Python3
# Python 3 program to find floor value# of mean in range l to rimport math# To find mean of range in l to rdef findMean(arr, l, r): # Both sum and count are # initialize to 0 sum, count = 0, 0 # To calculate sum and number # of elements in range l to r for i in range(l, r + 1): sum += arr[i] count += 1 # Calculate floor value of mean mean = math.floor(sum / count) # Returns mean of array # in range l to r return mean# Driver Codearr = [ 1, 2, 3, 4, 5 ] print(findMean(arr, 0, 2))print(findMean(arr, 1, 3))print(findMean(arr, 0, 4))# This code is contributed # by PrinciRaj1992 |
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).
Python3
# Python3 program to find floor value# of mean in range l to rimport math as mtMAX = 1000005prefixSum = [0 for i in range(MAX)]# To calculate prefixSum of arraydef calculatePrefixSum(arr, n): # Calculate prefix sum of array prefixSum[0] = arr[0] for i in range(1,n): prefixSum[i] = prefixSum[i - 1] + arr[i]# To return floor of mean# in range l to rdef findMean(l, r): if (l == 0): return mt.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 (mt.floor((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1)))# Driver Codearr = [1, 2, 3, 4, 5]n = len(arr)calculatePrefixSum(arr, n)print(findMean(0, 2))print(findMean(1, 3))print(findMean(0, 4))# This code is contributed by Mohit Kumar |
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!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000 neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
