# LeetCode 1015: Smallest Integer Divisible by K

## Problem Restatement

We need to find the smallest positive integer `N` consisting only of the digit `1` (a repunit) such that `N` is divisible by `k`.

In other words, find the smallest `n` such that:

```python
N = 111...1  (n ones)
N % k == 0
```

Return `n`, or `-1` if no such positive integer exists.

The official constraints state that `1 <= k <= 10^5`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `k` |
| Output | Length of the smallest repunit divisible by `k`, or `-1` |

Function shape:

```python
def smallestRepunitDivByK(k: int) -> int:
    ...
```

## Examples

Example 1:

```python
k = 1
```

`N = 1`, which is divisible by `1`.

Answer:

```python
1
```

Example 2:

```python
k = 2
```

No repunit is divisible by `2`. All repunits are odd numbers.

Answer:

```python
-1
```

Example 3:

```python
k = 3
```

`N = 111 = 3 * 37`, divisible by `3`.

Answer:

```python
3
```

## Key Insight

If `k` is divisible by `2` or `5`, no repunit can be divisible by `k`, because repunits always end in `1` (not an even number or multiple of 5).

Otherwise, we compute the remainder of `N_n = 111...1` (n ones) modulo `k`.

The recurrence is:

```python
N_n = N_{n-1} * 10 + 1
remainder_n = (remainder_{n-1} * 10 + 1) % k
```

By the pigeonhole principle, if we never hit remainder `0`, we will eventually see a repeated remainder after at most `k` steps. A repeated remainder means we are in a cycle and will never reach `0`.

## Algorithm

1. If `k % 2 == 0` or `k % 5 == 0`, return `-1`.
2. Start with `remainder = 0`.
3. For `n` from `1` to `k`:
   - `remainder = (remainder * 10 + 1) % k`.
   - If `remainder == 0`, return `n`.
4. Return `-1`.

## Correctness

By pigeonhole, there are only `k` possible remainders modulo `k`. If after `k` steps we have not found remainder `0`, then some remainder has appeared twice. This means the sequence of remainders is periodic and will never reach `0`.

## Edge Cases

- Duplicates usually matter; store counts when a set would lose necessary multiplicity.
- Update the frequency structure in the same order the invariant assumes.
- Check empty or one-element inputs if the problem allows them.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(k)` | At most `k` iterations |
| Space | `O(1)` | Constant space |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1

        remainder = 0
        for n in range(1, k + 1):
            remainder = (remainder * 10 + 1) % k
            if remainder == 0:
                return n

        return -1
```

## Code Explanation

Early exit for even or multiple-of-5 values:

```python
if k % 2 == 0 or k % 5 == 0:
    return -1
```

Compute remainders iteratively:

```python
remainder = (remainder * 10 + 1) % k
```

This avoids dealing with very large numbers.

Return the length when the remainder first reaches `0`:

```python
if remainder == 0:
    return n
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.smallestRepunitDivByK(1) == 1
    assert s.smallestRepunitDivByK(2) == -1
    assert s.smallestRepunitDivByK(3) == 3
    assert s.smallestRepunitDivByK(7) == 6
    assert s.smallestRepunitDivByK(5) == -1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `1` | `1` | `1 % 1 == 0` |
| `2` | `-1` | Repunits are odd |
| `3` | `3` | `111 = 3 × 37` |
| `7` | `6` | `111111 = 7 × 15873` |
| `5` | `-1` | Repunits don't end in 0 or 5 |