PROBLEM STATEMENT
An option found on most drum machines is the "Quantize" feature. This feature
is useful when entering patterns in real-time because it only allows beats to
occur at certain times. For example, say you want to enter a pattern
consisting of eighth-note hi-hats. Without "Quantize", you would have to enter
the beats with perfect timing to achieve your goal - a challenging feat for
those with sloppy rhythm... especially when using the small buttons on a drum
machine. However, if you set the "Quantize" interval to "eighth-note" and then
enter the beats, the machine will automatically move all your beats to their
closest eigth-note positions - it will not allow any beats to occur on a
non-eighth-note boundary. See the following diagram for a visual representation:
beat: 1 and 2 and 3 and 4 and
you: * * * * * *
quantize corrects it to:
beat: 1 and 2 and 3 and 4 and
you: * * * * * *
Consider a drum machine with its "Quantize" interval set such that beats may
only occur at times that are multiples of X, where X is an odd number. (So if
X = 5, beats may occur at the following times: 0, 5, 10, 15, 20, etc...).
Given a quantize interval and a int[] of times at which the user has entered a
beat, implement a function "quantize" that returns an int[] of corrected times
for the beats. The return value should be sorted in ascending order and each
element inside it should be unique (so if two user-inputted beats get corrected
to the same time, the resulting beat should only be represented once).
DEFINITION
Class: Quantize
Parameters: int[], int
Returns: int[]
Method signature (be sure your method is public): int[] quantize(int[] beats,
int X);
INPUT CONSTRAINTS
TopCoder will verify that all input constraints are met.
- beats will contain between 0 and 50 elements inclusive
- beats will be sorted in ascending order
- each element of beats will be unique
- each element of beats will be an int between 0 and 10000
- X will be an odd int between 3 and 101 inclusive
EXAMPLES:
beats: {3,9,14}
X: 5
Beats can only occur at multiples of 5. 3 is between two valid times - 0 and 5
- but it is closer to 5. 9 is closer to 10 than 5. 14 is closer to 15 than 10.
return value: {5,10,15}
-----------------------
beats: {0,1,11}
X: 11
0 and 11 are already at valid times. 1 should be corrected to 0 - but since
there's already a beat at 0, we don't double-count it.
return value: {0,11}
-----------------------
beats: {555,777,1000,1500}
X: 57
return value: {570, 798, 1026, 1482}