Proof: we only need to consider the first K candidates in [1, 11, 111, 1111, ...]
This problem is the second problem from Leetcode Contest 129. Among all the top-25 ranked participants, only 10 of them bounded their loop in K iterations. Thus
This problem is the second problem from Leetcode Contest 129. Among all the top-25 ranked participants, only 10 of them bounded their loop in K iterations. Thus, we have the strong motivation to mathematically prove the title of this post and bound our execution in K iterations. Otherwise, most people basically set an upper bound as 10^5 according to the note or just write a "while True" loop.\n\nIf this is true, the code in Python can be very elegant like this.\n```\ndef smallestRepunitDivByK(self, K: int) -> int:    \n    if K % 2 ==0 or K % 5==0:\n        return -1       \n    module = 1\n    for Ndigits in range(1, K+1):\n        if module % K == 0:\n            return Ndigits\n        module = (module * 10 + 1) % K\n    return 1234567890 # This line never executes\n```\nProof:\nIt is obvious that if K is the multiple of 2 or multiple of 5, N is definitely not multiple of K because the ones digit of N is 1. Thus, return -1 for this case.\n\nIf K is neither multiple of 2 nor multiple of 5, we have this theorem. \n\nTheorem: there must be one number from the K-long candidates list [1, 11, 111, ..., 111..111(with K ones)], which is the multiple of K. \n\nWhy? Let\'s think in the opposite way. Is it possible that none of the K candidates is the multiple of K?\n\nIf true, then the module of these K candidate numbers (mod K) must be in [1, .., K-1] (K-1 possible module values). Thus, there must be 2 candidate numbers with the same module. Let\'s denote these two numbers as N_i with i ones, and N_j with j ones and i<j.\n\nThus N_j-N_i = 1111...1000...0 with (j-i) ones and i zeros. N_j-N_i = 111..11 (j-i ones) * 100000..000 (i zeros). We know that N_i and N_j have the same module of K. Then N_j-N_i is the multiple of K. However, 100000..000 (i zeros) does not contain any factors of K (K is neither multiple of 2 nor multiple of 5). Thus, 111..11 (j-i ones) is the multiple of K. This is contradictory to our assumption that all K candidates including 111..11 (j-i ones) are not multiple of K.\n\nFinally, we know that there is at least one number, from the first K candidates, which is the multiple of K.
[]