Mean of range in array

Difficulty Level Medium
Frequently asked in Cadence India Expedia FreeCharge GreyOrange Roblox Snapchat Snapdeal Times Internet Yandex
Array Query ProblemViews 2057

Problem Statement

The problem “Mean of range in array” states that you are given an integer array and q number of queries. Each query contains the left and right as a range. The problem statement asks to find out the floor mean value of all the integers that come in a given range.

Example

array[] = {2, 5, 1, 6, 7, 8}

Query: {(1, 4), (0,2), (4,5)}
4 2 7

Explanation

(1,4) so mean value of 5,1,6,7 which is 4

(0,2) so mean value of 2,5,1 which is 2

(4,5) so mean value of 7,8 which is 7

Mean of range in array

 

Algorithm

  1. Create an array PreMeanSum and initialize its first value as the value of the given array.
  2. Traverse the array from 1 and store the sum of the previous value of PreMeanSum and the current value of the given array into the current value of PreMeanSum array.
  3. Get the left and right position of query and check if left position given is 0, if true then return the quotient of PreMeanSum[right] / right + 1.
  4. Else return the value of PreMeanSum[right]-PreMeanSum[left – 1]/ right – left +1.

Explanation

We have given an integer array and q number of queries. So, we have asked to return the floor value of the mean of the numbers that come in the given range. Thus, a simple approach that can be followed like for each query we will be traversing the array from the starting point of the range to the ending point of the range. And store the sum of all the values to a particular value. Suppose if we have to find the mean of (0, i). So that arr[i], we will have to summation of all the values from array zero, one up to the given ith value. Then we will return the quotient of that sum and the total number of values, of which sum is made.

But one disadvantage of that is, we have to traverse for the given range for each query if we have n queries. It will traverse the n number of time, but the approach which we are using it will return the answer of each query in constant time after we build the array once.

We will be building the array, for that we have declared the array PreMeanSum array. Then initialize the first element of the PreMeanSum array as the first value of the given array. We will traverse the array from one to the length of the array, the purpose of doing it is we have to store the sum of two adjacent value to the current value while traversing. That’s why we have copied that first value and starting from 1. We will receive the range as a starting point and ending point. After that we will be checking if the given left value is equal to 0, if true, then return the division of PreMeanSum[right] / right+1, simply sum/total number of values. Else we will return the division of difference of PreMeanSum[right]-PreMeanSum[left-1] and right-left+1. That will be the required answer.

Code

C++ code to find Mean of range in array

#include<iostream>
#include<math.h>

#define MAX 1000005
using namespace std;

int PreMeanSum[MAX];

void buildPreMean(int arr[], int n)
{
    PreMeanSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
}

int getMeanInRange(int l, int r)
{
    if (l == 0)
        return floor(PreMeanSum[r] / (r + 1));

    return floor( (PreMeanSum[r] - PreMeanSum[l - 1]) / (r - l + 1));
}

int main()
{

    int arr[] = {2,5,1,6,7,8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    buildPreMean(arr, n);
    cout << getMeanInRange(1, 4) << endl;
    cout << getMeanInRange(0, 2) << endl;
    cout << getMeanInRange(4, 5) << endl;
    return 0;
}

4
2
7

Java code to find Mean of range in array

class MeanInRange
{
    public static final int MAX = 1000005;

    static int PreMeanSum[] = new int[MAX];

    static void buildPreMean(int arr[], int n)
    {
        PreMeanSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
    }

    static int getMeanInRange(int l, int r)
    {
        if (l == 0)
            return (int)Math.floor(PreMeanSum[r] / (r + 1));

        return (int)Math.floor((PreMeanSum[r] -
                                PreMeanSum[l - 1]) / (r - l + 1));
    }

    public static void main(String[] args)
    {
        int arr[] = {2,5,1,6,7,8 };
        int n = arr.length;
        buildPreMean(arr, n);
        System.out.println(getMeanInRange(1, 4));
        System.out.println(getMeanInRange(0, 2));
        System.out.println(getMeanInRange(4, 5));
    }
}

4
2
7

Complexity Analysis

Time Complexity

O(n+q) where “q” is the number of queries to be performed as mean can be calculated in O(1) time complexity. O(n) time is required to precompute the PreMeanSum.

Space Complexity

O(n) where “n” is the number of elements in the array.

Translate »