TopCoder problem "ConcatenateNumber" used in SRM 390 (Division I Level One , Division II Level Two)



Problem Statement

    Given a positive integer number, concatenate one or more copies of number to create an integer that is divisible by k. Do not add any leading zeroes. Return the least number of copies needed, or -1 if it is impossible.
 

Definition

    
Class:ConcatenateNumber
Method:getSmallest
Parameters:int, int
Returns:int
Method signature:int getSmallest(int number, int k)
(be sure your method is public)
    
 

Constraints

-number will be between 1 and 1,000,000,000, inclusive.
-k will be between 1 and 100,000, inclusive.
 

Examples

0)
    
2
9
Returns: 9
At least 9 copies are needed, since 222222222 is divisible by 9.
1)
    
121
11
Returns: 1
121 is divisible by 11.
2)
    
1
2
Returns: -1
You can never get an even number by concatenating only 1's.
3)
    
35
98765
Returns: 9876
The resulting integer could be really big.
4)
    
1000000000
3
Returns: 3

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11124&pm=8589

Writer:

srbga

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Brute Force, Math, Simple Math