Smallest Integer Divisible by K
Real-world version: Stamping Ones Until It DividesThe statement here is our own: the same inputs, outputs and technique.
A machine stamps out numbers written with the digit 1 alone: 1, then 11, then 111, and so on without end.
Return the number of digits in the shortest of these that k divides exactly, or -1 when k divides none of them.
Examples
Example 1
- Input
- k = 7
- Output
- 6
The five shortest stamps all leave a remainder, and the sixth is seven times 15873.
Example 2
- Input
- k = 5
- Output
- -1
Every stamp ends in a one, while a multiple of five has to end in a five or a zero, so no stamp can ever divide.
Example 3
- Input
- k = 9
- Output
- 9
A multiple of nine has digits adding to a multiple of nine, so nine stamps are needed, and that number is nine times 12345679.
Constraints
- 1 <= k <= 10^5
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def smallest_repunit_div_by_k(k: int) -> int:public int smallestRepunitDivByK(int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's