SumAndProduct
SRM 431 · 2008-12-23 · by Gluk
SRM 431 · 2008-12-23 · by Gluk · Math
Problem Statement
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.
Constraints
- S and P will be between 1 and 1,000,000,000, inclusive.
Examples
0)
10 10 Returns: 1
The list contains only one element: 10.
1)
10 20 Returns: 2
2)
10 30 Returns: 3
3)
10 34 Returns: 3
4)
10 40 Returns: -1
103)
5 6 Returns: 2
The list contains two elements: 2 and 3.
104)
5 100 Returns: -1
No such list exists.
Submissions are judged against all 137 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SumAndProduct with a public method int smallestSet(int S, int P) · 137 test cases · 2 s / 256 MB per case