Java "fractile" method returning wrong output

Question

Directions: Given an int[] x and a percentage p (0 - 100), find the smallest valued element y of x so that at least percentage p elements of x are less than or equal to y.

Example 1:
x = {-3, -5, 2, 1}, p = 50 
Method should return -3 
Reason: 50% of the elements in x are less than or equal to -3:  -5 and -3

Example 2:
x = {7, 9, 2, -10, -6}, p = 50 
Method should return 2 
Reason: 60 percent of the elements in x are less than or equal to 2: 2, -10 and -6 
-6 would be wrong because only 40% of the elements are less than or equal
(100% of the elements are less than or equal to 9, but that isn't the smallest value)

Example 3:
x = {1,2,3,4,5,6,7,8,9,1,2,3,4,5,7,9,5,43,124,94}, p = 0
Method should return 1
Reason: Only 0% is needed, so in theory any number will do, but 1 is the smallest value

---

Here is what I've written for the method so far:

public static int fractile(int[] x, int p)
   {
      int smallestInt = x[0];            
      for (int i = 0; i < x.length; i++) {
         int testNum = x[i];
         int percentage;
         int count = 0;
         for (int j = 0; j < x.length; j++) {
            if (x[j] <= testNum)
               count++;
         }
         percentage = (count / x.length) * 100;
         if (testNum <= smallestInt && percentage >= p)
            smallestInt = testNum;
      }
      return smallestInt;
   }

But my output for my sample numbers comes out wrong:

INPUT: 
[6, 5, 4, 8, 3, 2]
40%
Method returns: 6
INPUT: 
[7, 5, 6, 4, 3, 8, 7, 6, 9, 10]
20%
Method returns: 7
INPUT: 
[3, 4, 2, 6, 7, 5, 4, 4, 3, 2]
60%
Method returns: 3

It's almost as if it's grabbing the first index and doesn't look at the numbers behind it but I can't figure out why.

What am I doing wrong?

Answer 1

Change your percentage to double/float and cast one of the variables in divide to double/float as well.

Something like:

double percentage=0.0;
...
percentage = ((double)count / x.length) * 100;

So the equation returns double/float.

--

Numeric Promotion Rules for primitive types

1. If two values have different data types, Java will automatically promote one of the values to the larger of the two data types.

2. If one of the values is integral and the other is floating-point, Java will automatically promote the integral value to the floating-point value’s data type.

3. Smaller data types, namely byte, short, and char, are first promoted to int any time they’re used with a Java binary arithmetic operator, even if neither of the operands is int.

4. After all promotion has occurred and the operands have the same data type, the resulting value will have the same data type as its promoted operands.

by Jeanne Boyarsky & Scott Selikoff - OCA study guide

Answer 2

In the line

percentage = (count / x.length) * 100;

count and x.length are both integer. Thus, dividing them results in an integer value, not a floating point number. Percentage will probably contain 0 or 100, and not some value in between.

Answer 3

What you need is selection algorithm that makes partition of array in given proportion.

Simple and fast one is QuickSelect

And I suspect that there is ready-to-use implementation in Java like C++ std::nth_element

Answer 4

For an array which is sorted from lowest to highest you can just multiply the length with the percentage to get the right index of the searched element. For more infos Quantiles

that will make your code shorter

 public static int fractile(int[] x, double p){   
   Arrays.sort(x);       
   int k = (int) Math.ceil(x.length*p)-1;
   return x[k];
}

Answer 5

You could try:

public static int fractile( int[] x, int p )
   {
        Arrays.sort(x);
        return x[Math.max((int) Math.ceil(x.length / 100.0 * p) - 1, 0)];
   }

This assumes you are allowed to manipulate the array. Sorting an array almost always makes manipulating it easier. This will work unless the array must stay as it is for whatever reason.

This code sorts the array, and since the initial input 'p' tells what percentage you're looking for, it looks at the approximate location in the array and returns the value stored there.

Answer 6

I have another implementation to that problem:

public static void main(String args[]){
  int[] a1 = {-3,-5,2,1};
  int[] a2 = {7,9,2,-10,-6};
  int[] a3 = {1,2,3,4,5,6,7,8,9,10};
  int[] a4 = {1,2,3,4,5,6,7,8,9,1,2,3,4,5,7,9,5,43,124,94};
  int[] a5 = {1};
  int p = 50;
  System.out.println(fractile(a1, p));
 }

 private static int fractile(int[] x, int p) {
  Arrays.sort(x);  
  double value0 = x.length / 100.0 * p;
  double value1 = Math.ceil(value0);
  int value2 = (int)value1; 
  int value3 = value2 - 1;
  int value4 = Math.max(value3, 0);
  return x[value4];
 }