Intution for 'cycle of remainders': 11 % 6 == 11111 % 6 == 11111111 % 6 == 3
While I had a gut feeling about the cyclic repetition of remainders, I had a hard time coming up with a proof (and thereby an efficient solution). While all the
While I had a gut feeling about the cyclic repetition of remainders, I had a hard time coming up with a proof (and thereby an efficient solution). While all the info is already there between other comments and the solution, I hope that the intution below helps.\n\nGiven a solution exists, finding it is not that hard: we keep creating the next larger number consisting of only \'1\'s and checking if it divides K without remainder:\n```python\ndef find_sol(K):\n\tn = count = 1\n\twhile True:\n\t    remainder = n % K\n\t\tif remainder == 0:\n\t\t    break\n\t\tn = 10 * n + 1\n\t\tcount += 1\t\n\treturn count\n```\n\nThe key question is: does a solution exist? Observations:\n* A multiple of an even number can never be an odd number --> K has to be odd\n* A similar case can be made for muliples of 5: they can only end in \'5\' or \'0\'\n\nFor numbers ending in 1, 3, 7, and 9, we have to think of something else. By the pigeonhole principle, it is clear that taking a series of numbers modulo K can only have K distinct remainders: remainder in [0..K-1].\nBut: how to prove that, as soon as we see a duplicate remainder, we actually have entered a **cycle of remainders**? Differently put: how can we prove that the **next remainder only depends on the previous remainder**, and not on the actual number \'n\'? Concretely:\n> Why does 11 % 6 == 11111 % 6 == 11111111 % 6 == 3?\n\nAll it really takes, is to look at two consecutive remainders with the equations already used in the code above:\n* Relation between \'n\' and the remainder: `n = x * k + rem`\n* Next number n: `next_n = 10 * n + 1`\n* the next remainder is calculated by: `next_rem = next_n % k`\n\nNow substitute the equations into one another:\n```python\nnext_rem = next_n % k\n         = (10 * n + 1) % k\n         = (10 * (x * k + rem) + 1) % k\n\t\t = ((10 * x * k) % k + (10 * rem) % k + 1 % k) % k  # distributive property of modulo\n\t\t = (10 * rem) % k + 1                               # any multiple of k is 0 when taken modulo k\n```\n\nSo, a future remainder depends only on the previous remainder, not on the actual value of n. Therefore: as soon as we see a remainder for the second time, we have entered a cycle.\nThis has the further benefit of making our code much more efficient, since we don\'t have to use any numbers larger than K:\n\n```python\nclass Solution:\n    def smallestRepunitDivByK(self, K: int) -> int:\n        if K % 2 == 0 or K % 5 == 0:\n            return -1  # multiples of 2, 4, 5, 6, 8 can never end with digit 1\n        \n        remainder = 0\n        for cnt in range(1, K+1):\n            remainder = (10 * remainder + 1) % K\n            if remainder == 0:\n                return cnt\n        return -1\n```\n\n**Analysis**\nO(K) time: at most K operations that take O(1) each\nO(1) space\n\n
['Python3']