TCHS-10-250

Problem Statement

Given a int[] x and a percentile p (between 0 and 100, inclusive), find the smallest element y in x such that at least p percent of the elements in x are less than or equal to y.

Definition

Class:	Fractile
Method:	fractile
Parameters:	int[], int
Returns:	int
Method signature:	int fractile(int[] x, int p)
(be sure your method is public)

Constraints

-

x will contain between 1 and 50 elements, inclusive.

-

Each element of x will be between -1000000 and 1000000, inclusive.

-

p will be between 0 and 100, inclusive.

Examples

0)

{-3,-5,2,1}

50

Returns: -3

50 percent of the elements in x are less than or equal to -3: -5 and -3.

1)

{7,9,2,-10,-6}

50

Returns: 2

60 percent of the elements in x are less than or equal to 2, and 40 percent are less than or equal to -6. At least 50% of the elements must be less than or equal to the answer, so the answer is 2.

2)

{1,2,3,4,5,6,7,8,9,10}

39

Returns: 4

4 gives 40%, but 3 gives 30%, which is not enough, so 4 is the answer.

3)

{1,2,3,4,5,6,7,8,9,1,2,3,4,5,7,9,5,43,124,94}

0

Returns: 1

The smallest element of x is 1 and it gives 5%.

4)

{1}

100

Returns: 1

1 is the only element of x, so there is no choice at all.

import java.util.Arrays;

public class Fractile {

	public int fractile(int[] x, int p) {
		int k = (int) Math.ceil(p * x.length / 100.0);
		Arrays.sort(x);
		return (k > 0) ? x[k-1] : x[0];
	}

}