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.
Definition
- Class:
- SecondLargestMultiple
- Method:
- find
- Parameters:
- long, int
- Returns:
- long
- Method signature:
- long find(long N, int B)
- (be sure your method is public)
Constraints
- N will be between 1 and 10^18, inclusive.
- B will be between 2 and 12, inclusive.
Examples
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.25
7
Returns: 800025