Mean Median Mode

Easy
0/40
Average time to solve is 10m
13 upvotes
Asked in companies
MicrosoftAmazonRippling

Problem statement

You are given an array 'ARR' of 'N' integers and you have to calculate 3 things for the given array:-

1. Mean - function mean(): This function should calculate the mean of the array.

2. Median - function median(): This function should calculate the median of the array.

3. Mode - function mode(): This function should calculate the mode of the array.

Note : 
It can be shown that Mean and Median is in the form of P/Q, where P and Q are coprime integers and Q != 0. You need to return P and Q.

For Mode, if the highest frequency of more than one element is the same, return the smallest element.

For Example, for the given array {1, 1, 2, 2, 3, 3, 4}, the mode will be 1 as it is the smallest of all the possible modes i.e 1, 2 and 3.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer T denoting the number of queries or test cases. 

The first line of every test case contains an integer N denoting the size of the input array.

The second line of every test case contains N single space-separated integers representing the elements of the input array.
Output format : 
For each test case, 
The first line of output will contain 2 single space-separated integers representing P, and Q for the Mean of the array.

The second line of output will contain 2 single space-separated integers representing P, and Q for the Median of the array.

The third line of the output will contain an integer representing the Mode of the array.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given functions.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5 
1 <= ARR[i] <= 10^6 

Where 'ARR[i]' denotes the 'ith' element of the array.

Time limit: 1 sec
Sample input 1 :
1
4  
3 3 1 4
Sample output 1 :
11 4
3 1
3
Explanation of sample input 1 :
To find the mean, we will take the sum of all the elements and then divide them by the total number of elements. Thus, (3 + 3 + 1 + 4)/4 = 11 / 4. Where P = 11 and Q = 4 and P, Q are coprime. 

To find the median, we will sort the array in ascending order and find the average of n/2 and (n/2 + 1)th number if N is even and (n+1)/2th number if N is odd. Thus, (3+3)/2 = 6 / 2. Thus P = 3 and Q = 1 and P, Q are coprimes.

To find the mode, we will find the element with the highest frequency which is 3 with a frequency of two and thus, the Mode is 3.
Sample input 2 :
1
5
7 6 5 5 3
Sample output 2 :
26 5 
5 1 
5
Hint

We can observe that everything asked from us can be done as it is done manually. 

For mean, all we need to care about is the sum of numbers and frequency. 

For median, we need the middle element when we take elements in ascending order.

For mode, all we need to do is to maintain the frequency of elements.

Approaches (1)
Brute force

For the mean and median of the array, we will first calculate both the results in N / D form where N denotes the numerator of the result and D denotes the denominator. Then for the P/ Q form where P and Q should be coprime, we will find the gcd of (N, D) and divide both N and D by the gcd. Thus P = N / gcd(N,D) and Q = D / gcd(N, D).

 

For the mean,

  1. Maintain the sum of the array elements and store it in a variable say Sum.
  2. Using the formulae Mean = (Sum of elements ) / ( Count of elements ), where N = Sum and D = Count. divide the Sum by N and return the answer.

 

For the median,

  1. Sort the array in ascending order.
  2. If the number of elements (N) is odd, Median is the (N+1)/2 th element. Thus N = array[(N+1)/2] and D = 1
  3. If the number of elements (N) is even, Median is the average of N/2th and (N/2 + 1)th element. Thus N = array[N/2] + array[(N+1)/2] and D = 2

 

For mode, 

  1. Maintain a hash table which stores the frequency of every element.
  2. Return the element with the highest frequency.
Time Complexity

N denotes the total numbers of elements in the array.

 

For mean, O(N) per test case

In the worst case, we will be iterating over all elements to find the sum which takes O(N) time.

 

For median, O(NlogN) per test case.

In the worst case, we will be sorting the array which takes O(NlogN) time.

 

For mode, O(N) per test case.

In the worst case, we will be iterating over all elements to store the frequency of each which takes O(N) time.

Space Complexity

For mean, O(1) per test case. 

In the worst case, only constant space is required.

 

For median, O(1) per test case. 

In the worst case, only constant space is required.

 

For mode, O(N) per test case. 

In the worst case, extra space is required to maintain a hashmap for N elements. 

Code Solution
(100% EXP penalty)
Mean Median Mode
Full screen
Console