Nice number theory question
\n/// If k is a multiple of 2 or 5, we cannot find such \'ans = 1..1\' such that\n/// ans is divisible by k because it\'s impossible for ans to have factor of 2
```\n/// If k is a multiple of 2 or 5, we cannot find such \'ans = 1..1\' such that\n/// ans is divisible by k because it\'s impossible for ans to have factor of 2 nor 5.\n/// Otherwise we claim during 1, 11, 111, 1...1 (k ones), there must be one number\n/// that is divisible by K. Proof by contradiction: if no such number, then for these\n/// k numbers, no number\'s module is 0. For the remaining choices 1, 2, 3, ... k -1,\n/// by Pigeonhole principle, there must be two numbers that share the same module.\n/// These two numbers x and y (x < y) has a diff y - x that has some zeroes as suffix.\n/// In other words, if x is i\'s ones, y is j\'s ones (i < j), then y - x = (j-i) ones * 10e(i),\n/// the 10e(i) part can only provide 2 and 5 factors, which is not divisible by k.\n/// So (j-i) ones is divisible by k, but j - i < k, so contradiction.\nclass Solution {\npublic:\n    int smallestRepunitDivByK(int K) {\n        if (K % 2 == 0 || K % 5 == 0) {\n            return -1;\n        }\n        int module = 0;\n        for (int i = 1; i <= K; ++i) {\n            module = (10 * module + 1) % K;\n            if (module == 0) {\n                return i;\n            }\n        }\n        return -1;\n    }\n};\n```
[]