DivisibleByDigits | Topcoder Archive

Problem Statement

Given an integer n, find the smallest integer that starts with n and is divisible by every non-zero digit of n (all in decimal notation).

Definition

Class:: DivisibleByDigits
Method:: getContinuation
Parameters:: int
Returns:: long
Method signature:: long getContinuation(int n)
(be sure your method is public)

Notes

An integer A starts with an integer B if the string representation of B is a prefix of the string representation of A (both in decimal notation with no leading zeroes).

Constraints

n will be between 1 and 1000000000, inclusive.

Examples

```
13
```
```
Returns: 132
```
We need a number that starts with 13 and is divisible by 1 (always true) and by 3. The smallest one is 132.
```
648
```
```
Returns: 648
```
If n is divisible by all its non-zero digits, the answer to the problem is n itself.
```
566
```
```
Returns: 56610
```
The resulting number must be divisible by 5, so it should end either with 0 or with 5. But a number ending with 5 is odd and can't be divisible by 6. So the last digit of the answer must be 0. In order to make the number divisible by 6, we need to put something before this 0, and the smallest appropriate digit is 1.
```
1000000000
```
```
Returns: 1000000000
```
```
987654321
```
```
Returns: 987654321360
```
```
83
```
```
Returns: 8304
```

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.