Generate the quotient
One can generate the quotient digits from least significant to most significant, because the problem has a recursive substructure.\n\nTo find K*Y=1111, we decom
One can generate the quotient digits from least significant to most significant, because the problem has a recursive substructure.\n\nTo find ```K*Y=1111```, we decompose Y into its digits say ```abcd```\n\n```\nK*abcd                     = 1111\nK*10*abc +K*d-1            = 1110, and K*d has to end with 1, so move the one from right to left\nK*10*abc +rest(d)          = 1110, we can simplify by introducing rest(d) = K*d-1, where rest(d) is divisible by 10\nK*abc    +rest(d)/10       = 111\nK*10*ab  +K*c+rest(d)/10-1 = 110, rest(c,d)=K*c+rest(d)/10-1, and rest(c,d) is divisible by 10\nK*ab     +rest(c,d)/10     = 11\nK*a      +rest(b,c,d)/10   = 1\n          rest(a,b,c,d)    = 0\n```\nIn general ```rest(next) = K*nextDigit + rest(previous)/10 - 1``` where rest ends with 0,\nand we can search for the unique nextDigit between ```0...9``` making rest ending in 0,\nsince every other part of the equation is known (```rest(previous)```  was recursively calculated,\nwith the base case 0).\n\n\n\n```\nclass Solution {\n    //111=37*3\n    //K*d+(K*j+(K*i-1)/10-1)/10 = 1\n    //    (3*3+(3*7-1)/10-1)/10\n    public int smallestRepunitDivByK(int K) {\n        if (K==1) return 1;\n        int len = 1;\n        var quotient = new StringBuilder();\n        for(long rest = 0; rest != 10; ++len){\n            boolean match = false;\n            for(int digit = 0; digit <= 9; ++digit){\n                if ((K*digit+rest/10)%10 == 1){\n                    rest = K*digit+rest/10-1;\n                    match = true;\n                    quotient.append((char)(digit+\'0\'));\n                    break;\n                }\n            }\n            if (!match) return -1;\n        }\n        System.out.println(quotient.reverse());\n        return len;\n    }\n}\n```
['Math', 'Greedy', 'Java']