# Smallest Integer Divisible by K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-integer-divisible-by-k)
Canonical: https://scaleengineer.com/dsa/problems/smallest-integer-divisible-by-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Hash Table
---
## Problem
Given a positive integer `k`, you need to find the **length** of the **smallest** positive integer `n` such that `n` is divisible by `k`, and `n` only contains the digit `1`.

Return _the **length** of_ `n`. If there is no such `n`, return -1.

**Note:** `n` may not fit in a 64-bit signed integer.

**Example 1:**

**Input:** k = 1
**Output:** 1
**Explanation:** The smallest answer is n = 1, which has length 1.

**Example 2:**

**Input:** k = 2
**Output:** -1
**Explanation:** There is no such positive integer n divisible by 2.

**Example 3:**

**Input:** k = 3
**Output:** 3
**Explanation:** The smallest answer is n = 111, which has length 3.

**Constraints:**

* `1 <= k <= 105`

# Approaches
## Brute Force with BigInteger
This approach simulates the process directly. We generate the numbers consisting of only ones (1, 11, 111, ...) and for each number, we check if it's divisible by `k`. Since these numbers can grow very large and exceed the capacity of standard integer types like `long`, we must use a data structure that supports arbitrary-precision arithmetic, such as Java's `BigInteger`.
**Time:** O(k^2). The loop runs up to `k` times. In each iteration `i`, the number `n` has `i` digits. `BigInteger` operations like multiplication and modulo on a number with `i` digits take roughly `O(i)` time. The total time is the sum of `O(i)` for `i` from 1 to `k`, which results in `O(k^2)`. · **Space:** O(k). We need to store the `BigInteger` `n`, which can have up to `k` digits. The space required is proportional to the number of digits.
**Pros:** Conceptually straightforward, directly translating the problem statement.
**Cons:** Inefficient due to the overhead of `BigInteger` operations.; Can lead to Time Limit Exceeded on platforms with strict time limits.; Requires external logic (capping iterations at `k`) to handle the no-solution case correctly.
### Explanation
The algorithm iteratively builds the numbers `n = 1, 11, 111, ...` and checks for divisibility by `k`.

```java
import java.math.BigInteger;

class Solution {
    public int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) {
            return -1;
        }
        BigInteger n = BigInteger.ONE;
        BigInteger kBigInt = BigInteger.valueOf(k);
        int length = 1;
        // We only need to check up to k times due to the Pigeonhole Principle.
        while (length <= k) {
            if (n.mod(kBigInt).equals(BigInteger.ZERO)) {
                return length;
            }
            n = n.multiply(BigInteger.TEN).add(BigInteger.ONE);
            length++;
        }
        return -1; // Should not be reached if k is not divisible by 2 or 5
    }
}
```
### Algorithm
- Initialize a `BigInteger` variable `n` to 1.
- Initialize a `length` variable to 1.
- Create a `BigInteger` representation of `k`.
- Start a loop that continues for at most `k` iterations. This limit is based on the Pigeonhole Principle, which guarantees that if a solution exists, it will be found within `k` steps.
- Inside the loop, check if `n` is divisible by `k` using the `mod` operation: `n.mod(k_big_int).equals(BigInteger.ZERO)`.
- If it is divisible, return the current `length`.
- If not, update `n` to the next number in the sequence: `n = n.multiply(BigInteger.TEN).add(BigInteger.ONE)`.
- Increment `length`.
- If the loop finishes, return -1.

## Optimal Approach: Iterative Modular Arithmetic
A much more efficient approach avoids dealing with large numbers altogether by using modular arithmetic. The key idea is that to check if a number `n` is divisible by `k`, we only need to know the remainder of `n` when divided by `k` (`n % k`). We can find a recurrence relation for the remainders and compute them iteratively.
**Time:** O(k). The loop runs at most `k` times. Each operation inside the loop (multiplication, addition, modulo) is a constant-time operation on standard integers. Therefore, the total time complexity is linear with respect to `k`. · **Space:** O(1). The algorithm uses only a few variables to store the current length and remainder, regardless of the size of `k`. The space used is constant.
**Pros:** Extremely efficient in both time and space.; Avoids large number arithmetic and potential overflows.; Provides a complete and correct solution by handling all edge cases.
**Cons:** The proof of correctness relies on number theory concepts (modular arithmetic, Pigeonhole Principle), which might not be immediately obvious.
### Explanation
Let `n_i` be the number formed by `i` ones. We have the relationship `n_i = n_{i-1} * 10 + 1`. If we take the modulo `k` on both sides, we get `n_i % k = ( (n_{i-1} % k) * 10 + 1 ) % k`. This means we can calculate the remainder for a number of length `i` using only the remainder of the number with length `i-1`. We never need to store the large number `n_i` itself.

The remainders can only take `k` possible values (0 to `k-1`). If we don't find a remainder of 0 within `k` iterations, the Pigeonhole Principle guarantees that at least one non-zero remainder must have been repeated. Once a remainder repeats, we are in a cycle and will never reach 0. Our initial check for divisibility by 2 and 5 ensures that a solution always exists if we pass that check, so the loop is guaranteed to find a solution within `k` iterations.

```java
class Solution {
    public int smallestRepunitDivByK(int k) {
        // If k is divisible by 2 or 5, no number made of 1s can be a multiple.
        if (k % 2 == 0 || k % 5 == 0) {
            return -1;
        }
        
        int remainder = 0;
        for (int length = 1; length <= k; length++) {
            // Calculate the remainder of the next number (e.g., 1, 11, 111, ...)
            // n_i = n_{i-1} * 10 + 1
            // rem_i = (rem_{i-1} * 10 + 1) % k
            remainder = (remainder * 10 + 1) % k;
            
            // If remainder is 0, we found the smallest multiple.
            if (remainder == 0) {
                return length;
            }
        }
        
        // This part should be unreachable if k is not divisible by 2 or 5.
        return -1;
    }
}
```
### Algorithm
- First, handle the impossible cases. A number consisting of only '1's can never be divisible by a number ending in 0, 2, 4, 5, 6, or 8. This means if `k` is divisible by 2 or 5, no solution exists. So, if `k % 2 == 0` or `k % 5 == 0`, return -1.
- Initialize a remainder variable `rem` to 0.
- Iterate for `length` from 1 to `k`.
- In each iteration, update the remainder using the formula: `rem = (rem * 10 + 1) % k`.
- If `rem` becomes 0, it means the number formed by the current `length` of ones is divisible by `k`. We have found the smallest length, so we return `length`.
- If the loop completes without finding a solution, it implies no solution exists (though this case is already covered by the initial check).

# Solutions
### Java

```java
class Solution {
public
  int smallestRepunitDivByK(int k) {
    int n = 1 % k;
    for (int i = 1; i <= k; ++i) {
      if (n == 0) {
        return i;
      }
      n = (n * 10 + 1) % k;
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution { public: int smallestRepunitDivByK ( int k ) { int n = 1 % k ; for ( int i = 1 ; i <= k ; ++ i ) { if ( n == 0 ) { return i ; } n = ( n * 10 + 1 ) % k ; } return - 1 ; } };
```

### Python

```python
class Solution:
    def smallestRepunitDivByK(self, k: int) -> int: n = 1 % k for i in range(1, k + 1): if n == 0: return i n = (n * 10 + 1) % k return - 1

```