SecondLargestMultiple
TCO21 Round 4 · 2021-04-13 · by misof
Problem Statement
In this problem we are interested in non-negative integers that have all digits distinct. For example, in base 10 the numbers 0, 47, 74, 13579, and 9876543201 all have this property.
The number 114 does not have this property in base 10, but it does have it in base 4 (where its digits are 1302).
You are given a positive integer N and the base B.
Let S(N,B) be the set of all non-negative integers that are multiples of N and have all digits distinct. Find and return the second largest number in S(N,B). If there is no such number, return -1 instead.
Constraints
- N will be between 1 and 10^18, inclusive.
- B will be between 2 and 12, inclusive.
1 10 Returns: 9876543201
We are in base 10. The largest multiple of 1 with distinct digits is clearly 9876543210, and the second largest is 9876543201.
12345 10 Returns: 9876012345
12345 3 Returns: -1
2 2 Returns: 0
The largest non-negative integer that has distinct digits in base 2 is 10 (base 2) = 2 (base 10). This is a multiple of 2, so it's the largest integer in S(2,2). The next non-negative integer that has distinct digits in base 2 is 1 (base 2) = 1 (base 10). This is not a multiple of 2. The final non-negative integer that has distinct digits in base 2 is 0 (base 2) = 0 (base 10). This is a multiple of 2 and thus the number we seek.
17 4 Returns: -1
The only multiple of 17 that has distinct digits in base-4 is the number 0. Thus, the second largest number with this property does not exist.
282458553905 11 Returns: 0
The only two multiples of this N with distinct digits in base 11 are zero and itself.
1768001 12 Returns: 8810065671066
This runs for about one second if I don't break the distinct digit test early, so anything with less than 5_000_000 multiples should run in time.
1628712 12 Returns: 736759274184
This one seemingly should have a pandigital solution but doesn't. The correct answer is 736759274184 = ba957234860_12.
Submissions are judged against all 292 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SecondLargestMultiple with a public method long long find(long long N, int B) · 292 test cases · 2 s / 256 MB per case