FourDistinctDigits | Topcoder Archive

Problem Statement

The time limit for this problem is 5 seconds.

You are given positive integers N. D and B. Find any positive integer X with the following properties:

X is a multiple of N.
When written in base B, X has exactly D digits.
When written in base B, X has at most four distinct digits.

Return a String of length D containing the base-B representation of X. Use 'A'-'Z' for digits 10-35, and 'a'-'z' for digits 36-61. For the given constraints a solution always exists, and any valid solution will be accepted.

Definition

Class:: FourDistinctDigits
Method:: find
Parameters:: long, int, int
Returns:: String
Method signature:: String find(long N, int D, int B)
(be sure your method is public)

Notes

The returned string cannot start with a zero.

Constraints

N will be between 1 and 10^11, inclusive.
D will be between 40 and 120, inclusive.
B will be between 5 and 62, inclusive.

Examples

```
4247
```
```
40
```
```
10
```
```
Returns: "4247424742474247424742474247424742474247"
```
The number 4247 has only three distinct digits in base 10. If we repeat those digits nine more times, we'll get a 40-digit number that is a multiple of 4247 and has only three distinct digits: 2, 4, and 7.
```
2
```
```
43
```
```
46
```
```
Returns: "Ad04400AdAdd4AdA404A0d44d04A40AAdAd4004dAdA"
```
Here we are looking for a valid 43-digit number in base 46. The character 'A' represents the digit 10, the character 'd' is the digit 39.

Returns: "62661141446422642461241446421222624162642612416"

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.