Last Updated: 24 Apr, 2021

Statistics From A Large Sample

Moderate

Asked in companies

Solve now

Problem statement

You have been given a sample of integers in the range [0, 255]. Since the sample is quite large, you are provided with an array/list “count” whose i-th element denotes the number of times ‘i’ appears in the sample.

You are supposed to calculate the following statistics :

1. minimum: The minimum element in the sample.

2. maximum: The maximum element in the sample.

3. mean: The average of the sample, calculated as the total sum of all elements divided by the total number of elements.

4. median:
If the sample has an odd number of elements, then the median is the middle element once the sample is sorted.
If the sample has an even number of elements, then the median is the average of the two middle elements once the sample is sorted.

5. mode: The number that appears the most in the sample. It is guaranteed to be unique.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains 256 space-separated integers where i-th integer denotes the frequency of i-th integer in the sample.

Output Format :

For each test case, print 5 space-separated values denoting minimum, maximum, mean, mode and median respectively. The values must be correct up to 5 decimal places.

Print the output of each test case in a separate line.

Note :

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
0 <= count[i] <= 1000    
Where count[i] is the i-th element of the “count” array/list.

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea of this approach is to iterate through the sample twice. In the first iteration, we will get the minimum, maximum, mean and mode. In the second iteration, we’ll find the median of the sample.

Algorithm

Create 5 variables “minimum”, “maximum”, “mean”, “median” and “mode”. Also, create two variables “sum” and “total” to store the sum and count of elements in the sample. Also, create a variable called “modeCount” and initialize it to zero to store the count of the mode.
Start iterating through the given array/list using the variable ‘i’.
- If frequency of the current element is non-zero then,
  - Update the “minimum” as minimum = min(minimum, count[i]).
  - Update the “maximum” as maximum = max(maximum, count[i]).
  - Update the “sum” as sum = sum + i * count[i].
  - Update the “total” as total = total + count[i].
  - Now, if the “modeCount” is less than the frequency of the current element, update the “mode” as mode = i and modeCount = count[i].
Update “mean” as “mean” = “sum” / “total”.
Create a variable called “cur” to store the count of elements.
Now, start iterating the given array/list to find the median using the variable ‘i’.
- We will perform the following steps if the frequency of the current element is non-zero.
- If “cur” is less than “count” / 2 then we’ll continue to loop. Because we are trying to find the (count/2)-th and ((count+1)/2) -th element.
- If “total” is odd then the current element will be the median. So “median” = i and break the loop.
- Otherwise, we’ll have to take the average two middle elements.
- If “median” is zero which means the current element is the first middle element.
  - If 2 * cur > total which means both middle elements is the current element. So “median” = i and break the loop.
  - Otherwise, the current element is the first middle element. So “median” = i
- Otherwise, the current element will be the second middle element. So “median” = “median” + i. Now, take the average so “median” = “median” / 2 and break the loop.
Return the “minimum”, “maximum”, “mean”, “median” and “mode”.

Solve now