Problem Breakdown
We need to find the smallest positive integer composed entirely of digit 1 (a repunit) that is divisible by . We return its length. If no such number exists, we return -1.
Key Constraints & Edge Cases:
- Overflow Risk: The problem states may not fit in a 64-bit signed integer. Constructing the full value of leads to overflow or excessive memory usage for large lengths (up to length ). We must track only the remainder modulo
K. Python handles arbitrary precision integers, but relying on modular arithmetic is necessary for efficiency and language-agnostic logic. - Divisibility by 2/5: Any number consisting solely of digit
1ends in an odd digit (specifically 1) and does not end in 0 or 5. Therefore, if shares a factor with 10 (i.e., is divisible by 2 or 5), no such repunit can be divisible by . We must return-1immediately for these cases to avoid infinite loops. - Input Range: . An algorithm iterating up to times is acceptable and efficient enough given the time limits (typically operations per second).
Intuition
A brute-force approach constructing N directly fails due to memory constraints. However, divisibility depends only on the remainder modulo .
Key Insight: We can generate repunits iteratively:
, .
Modulo arithmetic allows us update this as .
Since there are only possible remainders ( to ), by the Pigeonhole Principle, if we iterate more than times without finding a remainder of 0, and assuming is false (which guarantees termination for valid cases), no solution exists. For invalid cases (), the remainder will never be .
Approach
- Handle Impossible Cases: Check if
Kis divisible by 2 or 5. If so, return-1. This prevents infinite loops and handles edge cases like , , etc. - Iterative Remainder Tracking: Initialize current remainder (
rem) to (representing the number1). Set length counter to 1. - Loop Condition: While
rem != 0:- Update next value modulo
Kusing(rem * 10 + 1) % K. - Increment length counter.
- Update next value modulo
- Termination: Since we ruled out impossible cases, a solution is guaranteed to exist within iterations for valid inputs (specifically when ). If
rembecomes 0, return current length.
Complexity Analysis
- Time Complexity: . In the worst case where a solution exists, we iterate at most times because there are only distinct remainders modulo
K. For invalid cases (divisible by 2 or 5), it is due to early exit. - Space Complexity: . We use a constant amount of extra space for variables (
rem,length), regardless of input size.
Solution
class Solution:
def smallestRepunitDivByK(self, K: int) -> int:
# If K is divisible by 2 or 5, no repunit (only digit '1') can be divisible by it.
if K % 2 == 0 or K % 5 == 0:
return -1
rem = 1 % K
length = 1
# Iterate while remainder is not zero.
# Since we handled the impossible cases, a solution must exist within K steps for valid K.
while rem != 0:
rem = (rem * 10 + 1) % K
length += 1
return length
Edge Cases Handled
- K=1: Returns
lengthimmediately as remainder becomes 0 in first iteration (1%1 == 0). Correctly returns 1. - Divisible by 2 or 5: Explicitly checks and returns
-1, preventing infinite loops for invalid inputs like K=2, K=4, K=5, etc. - Large K (up to ): The loop runs at most times; Python’s arithmetic handles the modular updates efficiently without storing large integers explicitly.