# ---
# title: 1015. Smallest Integer Divisible by K
# id: problem1015
# author: Indigo
# date: 2021-01-30
# difficulty: Medium
# categories: Math
# link: <https://leetcode.com/problems/smallest-integer-divisible-by-k/description/>
# hidden: true
# ---
# 
# 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`
# 
# 
## @lc code=start
using LeetCode

function smallest_repunit_div_by_k(K::Int)
    (K % 2 == 0 || K % 5 == 0) && (return -1)
    r, len = 0, 1
    while true
        r = (10 * r % K + 1) % K
        r == 0 && return len
        len += 1
    end
end
## @lc code=end
