[Python3] ✔️ Less Math, More Intuition ✔️ | 2 Accepted Solutions | Intuitive
Important: A number containing only 1s cannot be divisible by 2 or 5. You can easily convince yourself that this is true since:\n A number divisble by 2 can onl
**Important**: A number containing only `1`s cannot be divisible by `2` or `5`. You can easily convince yourself that this is true since:\n* A number divisble by 2 can only end with `0`, `2`, `4`, `6`, or `8`.\n* A number divisble by 5 can only end with `0`, or `5`.\n\n\u2714\uFE0F **[Accepted] First Approach:** *Making use of Python Big Integer*\nHere, we solve the problem as if overflow does not exist. In fact, Python supports arbitrarily large numbers. However, this comes at the cost of speed/memory, but anyways this is the naive way of doing it:\n```\nclass Solution:\n    def smallestRepunitDivByK(self, k: int) -> int:\n        if not k % 2 or not k % 5: return -1\n        n = length = 1\n        while True:\n            if not n % k: return length\n            length += 1\n            n = 10*n + 1\n```\n\n\u2714\uFE0F **[Accepted] Second Approach:** *Using some math*\nTo improve that, the trick to avoid overflow is that we only need to store the remainder. A small proof for that can be found below:\n\n1. At every iteration, `n = kq + r` for some quotient `q` and remainder `r`.\n2. Therefore, `10*n + 1` = `10(kq + r) + 1` = `10kq + 10r + 1`.\n3. `10kq` is divisible by `k`, so for `10*n + 1` to be divisible by `k`, it all depends on if `10r + 1` is divisible by `k`.\n4. Therefore, we only have to keep track of `r`!\n\n```\nclass Solution:\n    def smallestRepunitDivByK(self, k: int) -> int:\n        if not k % 2 or not k % 5: return -1\n        r = length = 1\n        while True:\n            r = r % k\n            if not r: return length\n            length += 1\n            r = 10*r + 1\n```
['Math', 'Python', 'Python3']