TopCoder problem "DivisibleByDigits" used in SRM 375 (Division I Level One , Division II Level Three)



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

0)
    
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.
1)
    
648
Returns: 648
If n is divisible by all its non-zero digits, the answer to the problem is n itself.
2)
    
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.
3)
    
1000000000
Returns: 1000000000
4)
    
987654321
Returns: 987654321360
5)
    
83
Returns: 8304

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8318

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10794&pm=8318

Writer:

darnley

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Simple Math, Simple Search, Iteration