CentipedeSocks | Topcoder Archive

Problem Statement

You have C pet centipedes. You want to take them out for a walk, but it's quite cold. You want to give them socks to make them feel more comfortable.

Each of your centipedes has F feet. You have a large bin with centipede socks. The socks come in different colors, but your centipedes are quite picky and each of them requires to wear F socks of the same color.

You are given the ints C and F. You are also given the int[] sockCounts. Each element of sockCounts is the number of socks of one particular color you have in the bin.

Find and return the smallest X such that if you take any X socks out of the bin, it is guaranteed that you will be able to use some of them to keep all feet of all your centipedes warm. If there is no such X, return -1 instead.

Definition

Class:: CentipedeSocks
Method:: fewestSocks
Parameters:: int, int, int[]
Returns:: int
Method signature:: int fewestSocks(int C, int F, int[] sockCounts)
(be sure your method is public)

Constraints

C will be between 1 and 50, inclusive.
F will be between 1 and 100, inclusive.
sockCounts will have between 1 and 100 elements, inclusive.
Each element of sockCounts will be between 1 and 10^7, inclusive.

Examples

```
1
```
```
100
```
```
{1, 1, 1, 1, 100}
```
```
Returns: 104
```
One centipede with 100 feet. If you are really unlucky, you need to remove all 104 socks from the bin until you get all 100 pink ones.
```
1
```
```
100
```
```
{40, 50, 60, 70}
```
```
Returns: -1
```
You do not have 100 socks of any single color, so the poor centipede will be cold.
```
3
```
```
10
```
```
{12345}
```
```
Returns: 30
```
There are 12345 red socks in the bin. You just grab the first 30 and put 10 of them onto each of your centipedes.
```
2
```
```
3
```
```
{4, 4, 5}
```
```
Returns: 10
```
Two red, two blue, and five pink socks are still not enough to satisfy two three-legged centipedes.

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.