ConcatenateNumber
SRM 390 · 2008-02-02 · by srbga
SRM 390 · 2008-02-02 · by srbga · Brute Force, Math, Simple Math
Problem Statement
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.
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)
1000000000 6 Returns: 3
4)
1000000000 7 Returns: 3
5)
35 98765 Returns: 9876
The resulting integer could be really big.
Submissions are judged against all 159 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ConcatenateNumber with a public method int getSmallest(int number, int k) · 159 test cases · 2 s / 256 MB per case