Stats

SRM 139 · 2003-03-18 · by dgoodman

Class Name: Stats

Return Type: int

Method Name: range

Arg Types: (vector<int>)

Problem Statement

A common problem in dealing with data is to determine how "spread out" the data is. Two commonly used measures are the range (the maximum value minus the minimum value) and the standard deviation.

We propose using the Half-Range, which we define as the smallest number, N, such that at least half of the data values are contained within some interval of size N. (At least half of 17 or 18 values would be 9 or more.) The size of an interval is its maximum value minus its minimum value.

For example, if our data values are {1,2,4,5,6,8}, then the Half-Range is 2 because the interval from 4 to 6 (size 2) contains half of the values (4, 5, and 6) and furthermore, there is no interval whose size is less than 2 which contains half of the values.

Create a class Stats that contains a method range that is given a int[] data and returns its Half-Range.

Constraints

data will contain between 1 and 50 elements inclusive
each element of data will be between -1,000,000 and 1,000,000 inclusive

Examples

{9,2,3,8,8}
Returns: 1

The interval from 8 to 9 includes 3 of the 5 values.

{9,2,8,8}
Returns: 0

The interval from 8 to 8 contains 2 of the 4 values.

{1000000,-3,-1000000}
Returns: 999997

{231000,344,3440,34400,-1,19,19,802}
Returns: 345

{231000,344,3440,34400,-1,19,19,802,-60000}
Returns: 803

{-9,-8,-7,-6,0,0,0,2}
Returns: 2

Four values lie in the interval from 0 to 2

Submissions are judged against all 32 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Stats with a public method int range(vector<int> data) · 32 test cases · 2 s / 256 MB per case