GivenDigitSum
SRM 847 · 2023-06-22 · by misof
Problem Statement
Given are small positive integers D and S.
Return the smallest positive integer with the following properties:
- It has exactly D digits.
- The sum of its digits is exactly S.
- The product of its digits is zero.
If no such integer exists, return -1 instead.
Notes
- Everything in this problem is in base 10.
- The leading digit of a positive integer must always be non-zero.
Constraints
- D will be between 1 and 18, inclusive.
- S will be between 1 and 200, inclusive.
1 7 Returns: -1
The only 1-digit number with sum of digits 7 is obviously the number 7. However, the product of its digits isn't zero (it's 7), so there is no integer with all three required properties.
3 11 Returns: 209
Another integer with all three desired properties is 470: it has 3 digits, its digit sum is 4+7+0 = 11, and its digit product is 4*7*0 = 0. Remember that if multiple integers with the desired properties exist, you must return the smallest one among them. Thus, here only the answer 209 is accepted.
18 1 Returns: 100000000000000000
Watch out for integer overflow. The answer sometimes won't fit into a 32-bit integer variable.
11 11 Returns: 10000000019
3 99 Returns: -1
There is no 3-digit integer with digit sum 99.
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GivenDigitSum with a public method long long construct(int D, int S) · 30 test cases · 2 s / 256 MB per case