[Java/C++] Find 111....11 divisible by K
Intuition and Algorithm\n\nIf  W = 11\u2026\u202611 have t ones\nThen W * 10 +1  will have  t + 1  ones\n\nLet\u2019s create every number modulus K\n\nWe know:\
<strong>Intuition and Algorithm</strong>\n\nIf  <code>W = 11\u2026\u202611</code> have <code>t</code> ones\nThen <code>W * 10 +1 </code> will have  <code>t + 1</code>  ones\n\nLet\u2019s create every number modulus <code>K</code>\n\nWe know:\n* <code> (A*B+C)%K</code> = <code> (A%K * B%K + C%K) %K</code>\n\nIt is only necessary to iterate <code>K</code> times because we get a distinct result in each iteration, if the module is <code>0</code> then the number of iterations is the answer.\n\n<b>C++</b>\n<code>\n\n\tclass Solution {\n\tpublic:\n\t\tint smallestRepunitDivByK(int K) {\n\t\t\tfor(int i=1,val=1; i<=K; i++){\n\t\t\t\tif(val % K == 0) return i;\n\t\t\t\tval = (val*10 + 1)%K;\n\t\t\t}    \n\t\t\treturn -1;\n\t\t}\n\t};\n</code>\n\n<b>Java</b>\n<code>\n\n\tclass Solution {\n\t\tpublic int smallestRepunitDivByK(int K) {\n\t\t\tfor(int i=1,val=1; i<=K; i++){\n\t\t\t\tif(val % K == 0) return i;\n\t\t\t\tval = (val*10 + 1)%K;\n\t\t\t}    \n\t\t\treturn -1;\n\t\t}\n\t}\n</code>\n\nA small improvement is to validate if there is a loop.\n\n<b>C++</b>\n<code>\n\n\tclass Solution {\n\tpublic:\n\t\tint smallestRepunitDivByK(int K) {\n\t\t\tunordered_set<int>S;\n        \n\t\t\tfor(int i=1,val=1; i<=K; i++){\n\t\t\t\tif(val % K == 0) return i;\n\t\t\t\tif(S.find(val%K) != S.end())return -1; //exists a loop\n\t\t\t\tval = (val*10 + 1)%K;\n\t\t\t}\n        \n\t\t\treturn -1;\n\t\t}\n\t};\n</code>
[]