SumAndProduct | Topcoder Archive

Problem Statement

A list of non-negative numbers is called satisfactory if the sum of the numbers in the list is equal to S and the product of the numbers is equal to P. Find a satisfactory list with the least possible number of elements, and return its size. If no such list exists, return -1 instead. Please note that the list may contain non-integer numbers.

Definition

Class:: SumAndProduct
Method:: smallestSet
Parameters:: int, int
Returns:: int
Method signature:: int smallestSet(int S, int P)
(be sure your method is public)

Constraints

S and P will be between 1 and 1,000,000,000, inclusive.

Examples

```
10
```
```
10
```
```
Returns: 1
```
The list contains only one element: 10.
```
5
```
```
6
```
```
Returns: 2
```
The list contains two elements: 2 and 3.
```
5
```
```
100
```
```
Returns: -1
```
No such list exists.
```
100
```
```
1000000000
```
```
Returns: 9
```

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.