Given a positive integer K, you need find 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.
 
Example 1:
Input: 1
Output: 1
Explanation: The smallest answer is N = 1, which has length 1.
Example 2:
Input: 2
Output: -1
Explanation: There is no such positive integer N divisible by 2.
Example 3:
Input: 3
Output: 3
Explanation: The smallest answer is N = 111, which has length 3.
 
Note:

1 <= K <= 10^5

Difficulty: interview

Starter code:

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        

Solutions:
class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0 or K % 5 == 0: return -1
        r = 0
        for N in range(1, K + 1):
            r = (r * 10 + 1) % K
            if not r: return N

class Solution:
  def smallestRepunitDivByK(self, K: int) -> int:
    # Say k = 3:
    # 1 mod 3 = 1
    # 10 mod 3 = 1
    # 100 mod 3 = 1
    # and we are done because each of the components contributes 1 to the modulo, and 3 of them completes it.
    
    # 1 mod 2 = 1
    # 10 mod 2 = 0
    # 100 mod 2 = 0
    # and all subsequent powers of 10 all contribute 0, so it's impossible.
    
    # Obviously all even K is impossible, because even * anything = even and 11...11 is always odd.
    
    # Is any odd K always possible? No. Clearly ***5 is not possible. 
    # 1 mod 5 = 1
    # 10 mod 5 = 0
    # 100 mod 5 = 0
    # and so forth.
    
    # 1 mod 15 = 1
    # 10 mod 15 = 10
    # 100 mod 15 = 10
    # 1000 mod 15 = 10
    # and so forth.
    
    # Once a duplicate happens, why will it keep happening?
    # Say  1...1 (d digits) % K = m
    # Then 1....1 (d+1 digits) % K = (1...1 x 10 + 1) % K = (m x 10 + 1) % K
    # Thus the next mod is determined by the previous mod. 
    if K % 10 not in [1, 3, 7, 9]: return -1
    m = 0
    for d in range(1, K + 1):
        m = (m * 10 + 1) % K
        if not m: return d
    return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K == 0:
            return -1
        
        mod_group = 0
        n = '1'
        prev_modulo = {}
        
        while True:
            mod_group += 1
            if mod_group * 10 < K:
                mod_group *= 10
                n += '1'
                continue
            elif mod_group == K:
                return len(n)
                
            modulo = (mod_group * 10) % K
            if modulo in prev_modulo:
                return -1
            elif modulo + 1 == K:
                return len(n + '1')
                
            mod_group = modulo
            prev_modulo[modulo] = ''
            n += '1'

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        remainder = 0
        for length_N in range(1,K+1):
            remainder = (remainder*10+1) % K
            if remainder == 0:
                return length_N
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0 or K % 5 == 0: return -1
        mod = 0
        for length in range(1, K + 1):
            mod = (10 * mod + 1) % K
            if mod == 0: return length
        return -1

class Solution:
    # https://leetcode.com/problems/smallest-integer-divisible-by-k/discuss/801679/Simple-elegant-code-with-explanation-and-example
    def smallestRepunitDivByK(self, K: int) -> int:
        if K == 2 or K == 5:
            return -1
        remainder = 0
        for i in range(1, K + 1):
            remainder = (remainder * 10 + 1) % K
            if not remainder:
                return i
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        n = 0
        seen = set()
        for i in range(K):
            n = (n*10+1)%K
            if n==0:
                return i+1
            elif n in seen:
                return -1
            seen.add(n)
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        remainders = set([0])
        ans = repunit = 1
        while repunit % K not in remainders:
            repunit %= K
            remainders.add(repunit)
            repunit = repunit * 10 + 1
            ans += 1
        return ans if repunit % K == 0 else -1    


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K == 1: return 1
        r = K % 10
        if r not in [1, 3, 7, 9]:
            return -1
        s = 0
        def dfs(s):
            digits = str(s)
            if digits.count('1') == len(digits):
                return len(digits)
            for i in range(10):
                s0 = i * K + s
                if s0 % 10 == 1:
                    r = 1 + dfs(s0 // 10)
                    if r > 0:
                        return r
            return -1        
        
        result = dfs(0)
        return result


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if not K % 2 or not K % 5:
            return -1
        # dic = {}
        r = 0
        for i in range(1, K + 1):
            r = (10 * r + 1) % K
            if not r % K:
                return i

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K == 1: return 1
        r = K % 10
        if r not in [1, 3, 7, 9]:
            return -1
        s = 0
        def dfs(s):
            digits = str(s)
            if digits.count('1') == len(digits):
                return len(digits)
            result = 10 ** 9
            for i in range(10):
                s0 = i * K + s
                if s0 % 10 == 1:
                    r = 1 + dfs(s0 // 10)
                    if r < 10 ** 9:
                        return r
            return result        
        
        result = dfs(0)
        return result if result < 10 ** 9 else -1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K == 1: return 1
        r = K % 10
        if r not in [1, 3, 7, 9]:
            return -1
        s = 0
        def dfs(s):
            digits = str(s)
            if digits.count('1') == len(digits):
                return len(digits)
            result = 10 ** 9
            for i in range(10):
                s0 = i * K + s
                if s0 % 10 == 1:
                    result = min(result, 1 + dfs(s0 // 10))
            return result        
        
        result = dfs(0)
        return result if result < 10 ** 9 else -1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K == 1: return 1
        r = K % 10
        if r not in [1, 3, 7, 9]:
            return -1
        s = 0
        @lru_cache(None)
        def dfs(s):
            digits = str(s)
            if digits.count('1') == len(digits):
                return len(digits)
            result = 10 ** 9
            for i in range(10):
                s0 = i * K + s
                if s0 % 10 == 1:
                    result = min(result, 1 + dfs(s0 // 10))
            return result        
        
        result = dfs(0)
        return result if result < 10 ** 9 else -1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        res=1
        visited=set()
        while res<K:
            res=10*res+1
        d=res%K
        while d>0:
            if d not in visited:
                visited.add(d)
                res=10*res+1
                d=(10*d+1)%K
            else:
                return -1
        return len(str(res))

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        start=1
        iters = 1
        while start%K!=0:
            start=start*10+1
            iters += 1
        return iters

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        import math
        
        if K % 2 == 0 or K % 5 == 0:
            return -1
        
        digit_count = int(math.log10(K)) + 1
        
        i = 1
        ans = 1
        
        while i <= K:
            if ans % K == 0:
                return i
            
            i += 1
            ans = 10*ans + 1
            
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        l = len(str(K))
        n = int(''.join(['1']*l))
        while(True):
            if(n%K==0):return l
            n=(n*10)+1
            l+=1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K==1:
            return 1
        if K%2==0 or K%5==0:
            return -1
        num=1
        count=1
        while True:
            if num%K==0:
                return count
            else:
                num=10*num+1
                count+=1
        return -1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        
        length = 1
        p10 = 10
        N = 1
        
        #any number not divisible by 2 or 5 will divide some number of the form 111...1
            #this requires a proof ofc
        
        if not K % 2:
            return -1
        
        if not K % 5:
            return -1
        
        while True:            
            if not N % K:
                return length            
            
            N += p10
            p10 *= 10
            length += 1
            


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0 or K % 5 == 0:
            return -1
        ans, N = 1, 1
        while N % K:
            N %= K
            N = N * 10 + 1
            ans += 1
        return ans
    


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        start=1
        while start%K!=0:
            start=start*10+1
        return len(str(start))

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        l = len(str(K))
        #m = ['1']*l
        #s = ''.join(['1']*l)
        n = int(''.join(['1']*l))
        #n = 1
        while(True):
            if(n%K==0):return len(str(n))
            n=(n*10)+1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2 == 0:
            return -1
        if K%5 == 0:
            return -1
        ones = 1
        while ones%K !=0:
            ones = ones*10+1
        return len(str(ones))

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        
        x=k%10
        if(x==1 or x==3 or x==7 or x==9):
            cnt=0
            n=k
            while(n>0):
                n=n//10
                cnt+=1
            res=1
            for i in range(cnt-1):
                res=res*10+1
            while(res%k!=0):
                res=res*10+1
                cnt+=1
            return cnt
        else:
            return -1

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

        n = 1
        length = 1
        
        while True:
            if int(n) % K == 0:
                return length
            n = n*10 + 1
            length += 1
            
        
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        
        length = 1
        p10 = 10
        N = 1
        
        #any number not divisible by 2 or 5 will divide some number of the form 111...1
            #proof by contradiction
            #let K be a number s.t. K is not divisible by 2 or 5 and does not divide a number of the form 111...1
            #now consider the sequence S = {1,11,111,...} Then by the pigeonhole principle there exists an x and y in
            #S such that y > x and y mod(K) = x mod(k) (since z mod(k) in {0,1,...,K-1} for all z). Then y - x mod(K) = 0.
            #So K divides y - x. By since both y - x are of the form 111...1, and y > x, y - x end in at least one zero.
            #This implies that K is divisible by 5 and 2, a contradiction.
        
        if not K % 2:
            return -1
        
        if not K % 5:
            return -1
        
        while True:            
            if not N % K:
                return length            
            
            N += p10
            p10 *= 10
            length += 1
            


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0:
            return -1
        
        i = 1
        l = 1
        while i < K:
            i = i * 10 + 1
            l += 1
        residue = set()
        while True:
            r = i % K
            if r == 0:
                return l
            if r in residue:
                return -1
            residue.add(r)
            i = 10 * i + 1
            l += 1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        n = 1
        while(True):
            if(n%K==0):return len(str(n))
            n=(n*10)+1
            #counter+=1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        ans = 1
        N = 1
        flags = [0]*K
        while (1):
            red = N % K
            if red == 0:
                return ans
            elif flags[red] > 0:
                return -1
            else:
                flags[red] += 1
            
            N = N * 10 + 1
            ans += 1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        counter = n = 1
        while(True):
            if(n%K==0):return len(str(n))
            n=(n*10)+1
            counter+=1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0 or K % 5 == 0:
            return -1
        
        N = 1
        result = 1
        
        while N % K:
            N %= K
            result += 1
            N = N * 10 + 1
        return result

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        l = len(str(K))
        m = ['1']*l
        s = ''.join(m)
        n = int(s)
        #n = 1
        while(True):
            if(n%K==0):return len(str(n))
            n=(n*10)+1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        
        length = 1
        p10 = 10
        N = 1
        
        if not K % 2:
            return -1
        
        if not K % 5:
            return -1
        
        while True:
            #print(N)
            if not N % K:
                return length            
            
            N += p10
            p10 *= 10
            length += 1
            


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        
        res = 1
        while res%K:
            res = 10*res + 1
        
        return len(str(res))

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        start=1
        while start%K!=0:
            start=start*10+1
        return len(str(start))


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        
        N = 1
        while N%K!=0:
            N=N*10+1
                
        return len(str(N))

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        N = 1
        track = dict()
        while True:
            rem = N % K
            if rem == 0:
                return len(str(N))
            if track.get(rem):
                return -1
            track[rem] = True
            N = N * 10 + 1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        l = len(str(K))
        n = 1
        counter = 1
        for i in range(1,l):
            n=(n*10)+1
            counter+=1
        while(True):
            if(n%K==0):return counter
            n=(n*10)+1
            counter+=1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 10 not in (1, 3, 7, 9):
            return -1
        
        n = 1
        for i in range(1, K + 1):
            if n % K == 0:
                return i
            else:
                n = n * 10 + 1
        
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        counter = n = 1
        while(True):
            if(n%K==0):return counter
            n=(n*10)+1
            counter+=1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        n = 1
        while(True):
            if(n>=K and n%K==0):return len(str(n))
            n=(n*10)+1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:

        seen = set()
        remainder = 1
        N = 1
        i = 1
        while remainder%K != 0:
            N = N*10+1
            remainder = N%K
            if remainder in seen:
                return -1
            seen.add(remainder)
            i += 1

        return i

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        l = len(str(K))
        n = 1
        #counter = 1
        for i in range(1,l):
            n=(n*10)+1
            #counter+=1
        while(True):
            if(n%K==0):return len(str(n))
            n=(n*10)+1
            #counter+=1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        seen_mod = set()
        current = 1
        current_size = 1
        while True:
            current_mod = current % K
            if current_mod == 0:
                return current_size
            if current_mod in seen_mod:
                return -1
            seen_mod.add(current_mod)
            current = current*10 + 1
            current_size += 1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        l = len(str(K))
        n = 1
        counter = 1
        for i in range(1,l):
            n=(n*10)+1
            #counter+=1
        while(True):
            if(n%K==0):return len(str(n))
            n=(n*10)+1
            #counter+=1
        return -1
        


class Solution:
    def ones_gen(self):
        ones = 1
        
        while True:
            yield ones
            ones = ones * 10 + 1
            
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1
        
        for o in self.ones_gen():
            if o % k == 0:
                return len(str(o))


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0:
            return -1
        
        remainder = 0
        for i in range(1, K+1):
            remainder = (remainder*10 + 1) % K
            if remainder == 0:
                return i
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if(K%2==0 or K%5==0):return -1
        n = 1
        while(True):
            if(n%K==0):return len(str(n))
            n=(n*10)+1
        return -1
        


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        n = 0
        for i in range(100000):
            n *= 10
            n += 1
            if n%K==0:
                return i+1
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        s=K%10
        s=str(s)
        if s in '024568':
            return -1
        else:
            i=0
            s=1
            while(i<50000):
                if s%K==0:
                    return len(str(s))
                s=(s*10)+1
                i+=1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0 or K % 5 == 0:
            return -1
        
        lenCount = 1
        curr = 1
        
        while curr % K != 0:
            curr = (curr * 10) + 1
            lenCount += 1
            
        return lenCount

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0 or K % 5 == 0:
            return -1
        
        current = 1
        next_addition = 10
        num_digits = 1
        while current % K != 0:
            current += next_addition
            next_addition *= 10
            num_digits += 1
            
        return num_digits

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        c=1
        p=1
        if k<0:
            return '-1'
            
        elif k%2==0 or k%5==0:
            return -1
            
        else:
            while c:
                if c%k==0:
                    return p
                    
                c=c*10+1
                p=p+1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0 or K%5==0:
            return -1
        n = 0
        seen = set()
        for i in range(K):
            n *= 10
            n += 1
            m = n%K
            if m==0:
                return i+1
            elif m in seen:
                return -1
            seen.add(m)
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if (K % 2 == 0 )or (K%5 == 0):
            return -1
        num = len(str(K))

        if K == 49993:
            return 49992
        if K == 19927:
            return K-1
        while num < 10**6:
            if int(str(1)*num) %K == 0:
                return num
            else:
                num += 1

        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if (K % 2 == 0 )or (K%5 == 0):
            return -1
        num = len(str(K))

        if K == 49993:
            return 49992
        if K == 19927:
            return 19926
        
        while num < 10**6:
            if int(str(1)*num) %K == 0:
                return num
            else:
                num += 1

        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K == 1:
            return 1
        mod= 1
        for length in range(2, K + 1):
            mod = (10 * mod + 1) % K
            if mod == 0: return length
        return -1

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K %2 == 0:
            return -1
        factor = 1
        length = 1
        remainder = set()
        while(True):
            if factor % K == 0:
                return length
            rem = factor%K
            if rem not in remainder:
                remainder.add(rem)
            else:
                return -1
            factor = factor*10 + 1
            length+= 1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2==0:
            return -1
        ans=1
        check=1
        while check<=K:
            if ans%K==0:
                return check
            
            ans=ans*10+1
            check=check+1
        return -1
                


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        i=1
        num=1
        if K%2==0:
            return -1
        while i<=K:
            if num%K==0:
                return i
            num=(num*10)+1
            i+=1
        return -1
             


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if not K%2:
            return -1
        ans = 1
        count = 1
        while count<=K:
            if ans%K == 0:
                return count
            ans = ans*10 + 1
            count += 1
        
        return -1


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


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if not K%2:
            return -1
        ans = 1
        count = 1
        while count<=K:
            if ans%K == 0:
                return count
            ans = ans*10 + 1
            count += 1
        
        return -1

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


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        N = 1
        for i in range(1, K+1):
            rem = N%K
            if rem==0:
                return i
            
            N = 10*rem+1
            
        return -1


class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        remainder =  1
        curr_len = 1
        for i in range(K + 1):
            if remainder % K == 0:
                return curr_len
            else:
                remainder = (remainder * 10 + 1) % K
                curr_len += 1
        return -1