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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= k &lt;= 105


class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0: return -1
        n = 1
        leng = 1
        mapp = {}
        while True:
            rem = n % k
            if rem == 0: return leng
            if rem in mapp : return -1
            mapp[rem] = True
            n = n*10 + 1
            leng += 1
        
class Solution {
    public int smallestRepunitDivByK(int k) {
        // if (k % 2 == 0 || k % 5 == 0) return -1;  // this trick may save a little time
        boolean[] hit = new boolean[k];
        int n = 0, ans = 0;
        while (true) { // at most k times, because 0 <= remainder < k
            ++ ans;
            n = (n * 10 + 1) % k; // we only focus on whether to divide, so we only need to keep the remainder.
            if (n == 0) return ans; // can be divisible
            if (hit[n]) return -1; // the remainder of the division repeats, so it starts to loop that means it cannot be divisible.
            hit[n] = true;
        }
    }
}
class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if(k&1==0)return -1;
        long long val=0;

        for(int i=1; i<=k;i++)
        {
            // val=((val*10)+1);
            if((val=(val*10+1)%k)==0)return i;
        }
        return -1;
        
        
        
    }
};
/**
 * @param {number} k
 * @return {number}
 */
var smallestRepunitDivByK = function(k) {
    if( 1 > k > 1e6 ) return -1;
    let val = 0;
    for (let i = 1; i < 1e6; i++) {
        val = (val * 10 + 1) % k;
        if (val === 0) return i;
    }
    return -1;
};
Smallest Integer Divisible by K