C++ O(sqrt(k)) Beats 100%
Approach\n Describe your approach to solving the problem. \nSuppose $n$ consists of $m$ digits. Then, $n = 1 + 10 + \cdots + 10^{m - 1} = \frac{10^m - 1}{9}$. T
# Approach\n<!-- Describe your approach to solving the problem. -->\nSuppose $n$ consists of $m$ digits. Then, $n = 1 + 10 + \\cdots + 10^{m - 1} = \\frac{10^m - 1}{9}$. The necessary and sufficient condition is therefore $10^m \\equiv 1 \\ (\\mathrm{mod}\\ 9k)$. If $\\gcd(k, 10) = 1$ (in other words, $k$ is not divisble by $2$ or $5$), then such an $m$ must exist by Euler\'s theorem; otherwise, we immediately return $-1$.\n\nWe can use the baby-step giant-step algorithm to compute $m$ in time $\\mathcal{O}(\\sqrt{k})$. \nIf you\'re not familiar with it, we write $m = Sa - b$ for some $a > 0$ and $0 \\leq b < S$, where $S$ is the square root of our modulus (in this case, $9k$). Then, $10^{Sa - b} \\equiv 1 \\ (\\mathrm{mod}\\ 9k) \\implies 10^{Sa} \\equiv 10^{b} \\ (\\mathrm{mod} \\ 9k)$, so we can compute all values of $10^b$, store them in a hashmap, and find the first collision when iterating through values of $10^{Sa}$ in increasing order. Since $m \\leq \\Phi(9k) < 9k - 1$, we will need at most $\\mathcal{O}(\\sqrt{k})$ steps to get our answer.\n\n# Complexity\n- Time complexity: $\\mathcal{O}(\\sqrt{k})$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $\\mathcal{O}(\\sqrt{k})$\n\n# Code\n```\nclass Solution {\n    inline int discrete_log(int x, int M) {\n        int S = (int)sqrt(M);\n        unordered_map<int, int> rhs_powers;\n\n        for (int i = 0, p = 1; i < S; ++i) { \n            rhs_powers[p] = i;\n            p = (long long)p * x % M;\n        }\n\n        int pow_xs = 1;\n        for (int i = 1; i <= S; ++i) {\n            pow_xs = (long long)pow_xs * x % M;\n        }\n\n        for (int i = S, p = pow_xs;; i += S) {\n            if (rhs_powers.count(p % M)) return i - rhs_powers[p % M];\n            p = ((long long)p * pow_xs) % M;\n        }\n    }\npublic:\n    int smallestRepunitDivByK(int k) {\n        if (k % 2 == 0 || k % 5 == 0) return -1;\n        return k == 1 ? 1 : discrete_log(10, 9 * k);\n    }\n};\n```
['C++']