testcase failing for -- Mean median mode question asked in competitive programming

user_4860775 0
Viewed 1507

I got below question in one of my company entrance exam. All testcases were passing except 4 testcase. Can someone try to lookout what can be the possible scenario, which might be failing. Question and solutions are given below:

Mean, Median and Mode

Given 'n' integers find their mean median and mode. You are requested to fill in a function that takes an input integer 'input1' (1<=input1<=1000) and an integer array input2[] containing 'input1' integers and returns output1 as the mean output2 as the median and output3 as the mode.

The mean and median must be correct to six decimal places.

Mean: Defined as the avearge of all numbers in array.

Median : Define as the middle element of array.

If n is even the median is the average of the two middle elements If n is odd, the median is the middle element of array.

Note : For finding the median,elements in the array have to be listed in numerical order from smallest to largest.

Mode: Defined as the number in the array with highest frequency. If many numbers have the same highest frequency then the mode is calculated by breaking the ties in favour of the smallest of the numbers.

Input specifications :

Input1 : Integer in the range of 1<=input1<=1000 denoting length of input array.

Input2 : Integer input array.

Output specifications :

Return output1(double) variable as the mean.

Return output2(double) variable as the median.

Return output3(int) variable as the mode.

Sample Test Case 1:

input1: 3

input2: {1,2,3}

Output : 2.000000,2.000000,1

Sample Test Case 2:

input1: 5

input2: {41, 18467, 6334, 26500, 19169 }

Output : 14102.200000,18467.000000,41

package algo;
import java.util.*;

public class MeanMedianMode 
{
    // Function for calculating mean
    public static double findMean(int n , int a[])
    {
        int sum = 0;
        for (int i = 0; i < n; i++)

        sum += a[i];

    return (double)sum / (double)n;
}

public static double findMedian(int n, int a[])
{
    // First we sort the array
    Arrays.sort(a);

    // check for even case
    if (n % 2 != 0)
        return (double)a[n / 2];

    return (double)(a[(n - 1) / 2] + a[n / 2]) / 2.0;
}

public static int findMode(int n, int a[] ) {
    int maxValue=0, maxCount=0;

    for (int i = 0; i < a.length; ++i) {
        int count = 0;
        for (int j = 0; j < a.length; ++j) {
            if (a[j] == a[i]) ++count;
        }
        if (count >  maxCount) {
            maxCount = count;
            maxValue = a[i];
        }
    }

   return maxValue;
 }

// Driver code
public static void main(String args[])
{
    int a[] = { 41, 18467, 6334, 26500, 19169 };
    int n = a.length;

    System.out.println("Mean = " + String.format("%.6f", findMean(n, a)));
    System.out.println("Median = " + String.format("%.6f", findMedian(n, a)) );
    System.out.println("Mode = " + findMode(n, a));
}
}

Edit: Can there be any scenario of bimodal, trimodal array like {1,1,2,2} and {1,1,2,2,3,3} where mode can be {1,2} or {1,2,3} . I am asking this since return type will be int[] in this case, but in question it was specifically mentioned that return type must be int.

algorithm java
1 Answers

The issue is in findMode. You don't handle the case where there are multiple numbers with the same highest frequency. The problem statement says:

If many numbers have the same highest frequency then the mode is calculated by breaking the ties in favour of the smallest of the numbers.

The simplest solution is to store the mode value only when it is lower than the previous mode value - initializing the mode value to the highest possible value.

public static int findMode(int n, int a[] ) {
    int maxValue = Integer.MAX_VALUE; // Note that a[0]+1 would also work
    int maxCount = 0;
    
    for (int i = 0; i < a.length; ++i) {
        int count = 0;
        for (int j = 0; j < a.length; ++j) {
            if (a[j] == a[i]) ++count;
        }
        if (count >= maxCount && a[i] < maxValue) {
            maxCount = count;
            maxValue = a[i];
        }
    }
    
    return maxValue;
}

Note, your algorithm is inefficient in that it will count the same number each time it appears in the list. For example, if 1 appears in the list 100 times, it will count the frequency of 1 100 times.

EDIT: Ok, because you sort the array, this is not the issue.

The only other thing I can think of is that you have integer overflow in findMean. The max value an int can hold is 2,147,483,647. Since the arrays can be large (up to 1000 elements) it is very possible int sum can't hold the value. Try changing to double sum = 0;

user_6695760
Related