C++ 3 lines, O(K) | O(1)
Intuition\nWe can do a long division until our modulo is zero. If the number is not divisible, at some point we will encountered a modulo that we have seen befo
# Intuition\nWe can do a long division until our modulo is zero. If the number is not divisible, at some point we will encountered a modulo that we have seen before.\n# O(K) Memory Solution\nFor every digit, we track modulo ```m``` and add one more ```1``` (```(m % K) * 10 + 1```). We can ignore division results for this problem.\nTrack all moduli in ```seen``` and stop if the value has been seen before (in other words, we detected a loop).\nIf we ever seen ```m == 0```, then the integer is divisible, and number of digits is number of different moduli we encountered.\n```\nint smallestRepunitDivByK(int K) {\n  vector<bool> seen(K);\n  for (int m = 1; !seen[m % K]; m = (m % K) * 10 + 1) seen[m % K] = true;\n  return seen[0] ? count_if(begin(seen), end(seen), [](bool s) { return s; }) : -1;\n}\n```\n## Complexity Analysis\nRuntime: O(K). We can have maximum K moduli before we enter a loop.\nMemory: O(K). We need to track K moduli.\n# Constant Memory Solution\nAlternativelly, we can just always perform up to K iterations and check if our modulo ```m``` is zero. As the solution above demonstrates, we need maximum K steps to find a solution or we enter a loop.\n```\nint smallestRepunitDivByK(int K) {\n  for (int m = 1, N = 1 % K; N <= K; m = (m * 10 + 1) % K, ++N)\n    if (m == 0) return N;\n  return -1;\n}\n```\n## Complexity Analysis\nRuntime: O(K). We perform maximum K iterations.\nMemory: O(1).\n
[]