[Python3] group theory
Write [(N+1) many 1s]111....1 = (10^(N+1) - 1)/9 (simple geometric series expansion)\n\nIt is easy to see that there exists N such that K divides (10^(N+1) - 1)
Write [(N+1) many 1s]111....1 = (10^(N+1) - 1)/9 (simple geometric series expansion)\n\nIt is easy to see that there exists N such that K divides (10^(N+1) - 1)/9 if and only if 10^(N+1) = 1 (mod 9K), i.e. 10^(N+1) is the identity in the multiplicative group Z_{9K}\\*. Z_{9K}\\* consists of elements coprime with 9K. Hence the algorithm returns -1 if gcd(10,9K) != 1\n\nIf gcd(10,9K) = 1, then the group action f(x) = 10x acts transitively on Z_{9K}\\* and we know that the answer is the size of the orbit of 1 under f.\n\n```\nclass Solution:\n    def gcd(self, a: int, b: int) -> int:\n        if(b == 1):\n            return a\n        else:\n            return gcd(b, a%b)\n    \n    def smallestRepunitDivByK(self, K: int) -> int:\n        D = 9*K\n        g = self.gcd(10, D)\n        \n        if g != 1:\n            return -1\n        \n        else:\n            k = 1\n            current = 1\n            \n            while True:\n                current = current*10 % D\n                if current == 1:\n                    return k\n                else:\n                    k += 1\n```
[]