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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Mathematics

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:
		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:

	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:
		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
		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:
			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:
		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:
		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:
		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:
		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:
		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 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 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
		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:
			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:
				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