Domain 2MediumMEDIUM

Smallest Integer Divisible by K

Find the length of the smallest repunit divisible by K using modular arithmetic, returning -1 if K is even or a multiple of 5.

Domain: medium•Updated: 2026-09-06
#Modular Arithmetic#Variables#O(K)#O(1)

Problem Breakdown

We need to find the smallest positive integer NN composed entirely of digit 1 (a repunit) that is divisible by KK. We return its length. If no such number exists, we return -1.

Key Constraints & Edge Cases:

  • Overflow Risk: The problem states NN may not fit in a 64-bit signed integer. Constructing the full value of NN leads to overflow or excessive memory usage for large lengths (up to length ≈K\approx K). 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 1 ends in an odd digit (specifically 1) and does not end in 0 or 5. Therefore, if KK shares a factor with 10 (i.e., is divisible by 2 or 5), no such repunit can be divisible by KK. We must return -1 immediately for these cases to avoid infinite loops.
  • Input Range: K≤105K \le 10^5. An algorithm iterating up to O(K)O(K) times is acceptable and efficient enough given the time limits (typically ≈108\approx 10^8 operations per second).

Intuition

A brute-force approach constructing N directly fails due to memory constraints. However, divisibility depends only on the remainder modulo KK.

Key Insight: We can generate repunits iteratively: R1=1R_1 = 1, Rn=Rn−1×10+1R_n = R_{n-1} \times 10 + 1. Modulo arithmetic allows us update this as remn=(remn−1×10+1)%K\text{rem}_n = (\text{rem}_{n-1} \times 10 + 1) \% K. Since there are only KK possible remainders (00 to K−1K-1), by the Pigeonhole Principle, if we iterate more than KK times without finding a remainder of 0, and assuming gcd⁡(K,2)=gcd⁡(K,5)\gcd(K, 2)=\gcd(K,5) is false (which guarantees termination for valid cases), no solution exists. For invalid cases (K%2==0∨K%5==0K \% 2 == 0 \lor K \% 5 == 0), the remainder will never be 00.

Approach

  1. Handle Impossible Cases: Check if K is divisible by 2 or 5. If so, return -1. This prevents infinite loops and handles edge cases like K=2K=2, K=4K=4, etc.
  2. Iterative Remainder Tracking: Initialize current remainder (rem) to 1%K1 \% K (representing the number 1). Set length counter to 1.
  3. Loop Condition: While rem != 0:
    • Update next value modulo K using (rem * 10 + 1) % K.
    • Increment length counter.
  4. Termination: Since we ruled out impossible cases, a solution is guaranteed to exist within KK iterations for valid inputs (specifically when gcd⁡(K,2)=gcd⁡(K,5)\gcd(K, 2)=\gcd(K,5)). If rem becomes 0, return current length.

Complexity Analysis

  • Time Complexity: O(K)O(K). In the worst case where a solution exists, we iterate at most KK times because there are only KK distinct remainders modulo K. For invalid cases (divisible by 2 or 5), it is O(1)O(1) due to early exit.
  • Space Complexity: O(1)O(1). 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 length immediately 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 10510^5): The loop runs at most KK times; Python’s arithmetic handles the modular updates efficiently without storing large integers explicitly.