[Python] Math, Pigeon holes, explained
First of all, let us notice, that if number is divisible by 2 or by 5, then we need to return -1 immediatly, because number ending with 1 can not divide by 2 or
First of all, let us notice, that if number is divisible by `2` or by `5`, then we need to return `-1` immediatly, because number ending with `1` can not divide by `2` or `5`. From now on we assume, that `K` is not divisible by `2` or `5`. Let us consider numbers:\n\n`1`\n`11`\n`111`\n...\n`111...111`,\n\nwhere were have `K` ones in the last group. Then, there can be only two cases:\n1. All reminders of given numbers when we divide by `K` are different.\n2. Some two reminders are equal.\n\nIn the first case, we have `K` numbers and also `K` possible reminders and they are all different, it means, that one of them will be equal to `0`.\n\nIn the second case, two numbers have the same reminder, let us say number `11...1111` with `a` ones and `111...11111` with `b` ones, where `b > a`. Then, difference of these two numbers will be divisible by `K`. What is the difference? It is number `11...1100...000` with `b-a` ones and `a` zeroes at the end. We already mentioned that `K` is not divisible by `2` or `5` and it follows, that `11...111` divisible by `K` now, where we have `b-a` ones.\n\nSo, we proved the following statements: **if K not divisible by 2 and 5, then N <= K**. What we need to do now is just iterate through numbers and stop when we find number divisible by `K`. To simplify our cumputation, we notice, that each next number is previous multiplied by `10` plus `1`.\n\n**Complexity**: time complexity is `O(n)`, space is `O(1)`.\n\n```\nclass Solution(object):\n    def smallestRepunitDivByK(self, K):\n        if K % 2 == 0 or K % 5 == 0: return -1\n        rem, steps = 1, 1\n        while rem % K != 0:\n            rem = (rem*10 + 1) % K\n            steps += 1\n        return steps\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Math']