DollSets | Topcoder Archive

Problem Statement

A doll vendor has just received a shipment of dolls from the factory. Their sizes are given in the int[] dollSizes. The vendor can only sell dolls in sets of two such that one doll is K times as large as the other. What is the maximum number of sets that the vendor can assemble? Each doll can only be used in a single set.

Definition

Class:: DollSets
Method:: maximumQuantity
Parameters:: int[], int
Returns:: int
Method signature:: int maximumQuantity(int[] dollSizes, int K)
(be sure your method is public)

Constraints

dollSizes will contain between 1 and 50 elements, inclusive.
Each element in dollSizes will be between 1 and 1000000, inclusive.
K will be between 1 and 25, inclusive

Examples

```
{1,2,1,2,4}
```
```
2
```
```
Returns: 2
```
There are two possible ways to construct two sets: ({1,2},{1,2}) and ({1,2},{2,4}).
```
{5,4,3,2,1}
```
```
2
```
```
Returns: 1
```
You can construct either set {1,2} or set {2,4}.

{5,4,1,2,3,4,5,67,8,9,8,7,15,12}

Returns: 3

```
{1}
```
```
25
```
```
Returns: 0
```
```
{1,9,81,729,1,81}
```
```
9
```
```
Returns: 2
```
```
{1,2,2}
```
```
1
```
```
Returns: 1
```

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.