Distincter | Topcoder Archive

Problem Statement

We are given a int[] sequence containing a sequence of numbers. In a single operation, we can either increment or decrement the value of a single element by 1. Determine the minimum number of operations we must perform before the sequence contains at least K distinct elements.

Definition

Class:: Distincter
Method:: disperse
Parameters:: int[], int
Returns:: int
Method signature:: int disperse(int[] sequence, int K)
(be sure your method is public)

Notes

Note that we can create negative elements during the process.

Constraints

sequence will contain between 1 and 50 elements, inclusive.
Each element in sequence will be between 1 and 1000, inclusive.
K will be between 1 and the number of elements in sequence, inclusive.

Examples

```
{5, 1, 3}
```
```
2
```
```
Returns: 0
```
The sequence already has two distinct elements.
```
{1, 1, 1, 1, 1, 1, 1}
```
```
5
```
```
Returns: 6
```
Some elements can become negative.
```
{1, 1, 1, 1, 1, 2, 3}
```
```
6
```
```
Returns: 6
```
```
{8, 9, 7, 8, 7, 9, 7}
```
```
7
```
```
Returns: 7
```
```
{1, 2, 3, 4, 4, 5, 7, 7, 8}
```
```
9
```
```
Returns: 4
```
The optimal way to make 9 distinct elements is to increase one of the 4s two times and increase one of the 7s two times.

{576, 571, 571, 572, 575, 572, 571, 568, 573, 572, 569, 572}

Returns: 12

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.