Mean median mode of unsorted array
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.

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

Question

Mean median mode of unsorted array

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.

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

Accepted Answer

The mean was easy to compute calculating the sum of the entire array, then I sorted the array for median and checked the size of the array. If the size was odd I returned the middle element else I returned the average of the two middle elements. For mode, I maintained a frequency array and returned the lowest element with maximum frequency.

Accepted Answer

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,

Maintain the sum of the array elements and store it in a variable say Sum.
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,

Sort the array in ascending order.
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
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,

Maintain a hash table which stores the frequency of every element.
Return the element with the highest frequency.

Space Complexity: O(1)Explanation:

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.

Time Complexity: O(1)Explanation:

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.

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 :

Input format :

Output format :

Note :

Constraints :

Top Microsoft Corporation Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Microsoft Corporation Software Developer Intern