[Java Solution, Faster than 100%] Easy understand with pigeonhole principle
We start with a math problem, which can be easily proved by the Pigeonhole principle: \nGiven a positive k such as gcd(k, 10) = 1. Prove that there is a positiv
We start with **a math problem**, which can be easily proved by the Pigeonhole principle: \nGiven a positive k such as gcd(k, 10) = 1. Prove that there is a positive integer n with all digits equal to 1 such that: n is divisible by k. \n\nWe can easily see that by Pigeonhole principle: in k + 1 numbers 1, 11, 111, ..., 111..1 (k + 1 digts 1) \n-> there will be two number that has the same remainder when divided by k, for example, 11...1 (p digits 1) and 11...1 (q digits 1) ( p > q). \nThen, (111...1 - 111...1) % k = 0 or 11...1 * 10^q % k = 0. So 11...1 (p - q digit 1) % k = 0 (because gcd(k, 10) = 1)\n\n**So back to origin problem**, we can easily find the smallest integer n by a loop from 1 to k + 1, each time we will recalculate the remainder of the current number divided by k, and return the result when remainder = 0. The solution is only **O(k)** time complexity. \nDon\'t forget to check ***if (k, 10) != 1*** we will not have any solution. (because an integer n is divisible by 2 must be even and divisible by 5 must have end digit is 0 or 5). \n\n```\nclass Solution {\n    public int smallestRepunitDivByK(int k) {\n        if(k % 2 == 0 || k % 5 == 0) {\n            return -1;\n        }\n        int ans = 1, cur = 1;\n        for(int i = 1; i <= k + 1; i++) {\n            if(cur % k == 0) {\n                return ans;    \n            }\n            ans++; cur = (cur * 10 + 1) % k;\n        }\n        return ans;\n    }\n}\n```
['Math']