[Java] 1ms Pigeonhole Division w/ Explanation
\nclass Solution {\n    public int smallestRepunitDivByK(int K) {\n        if(K%2 ==0 || K % 5 == 0){\n            return -1;\n        } else {\n            int
```\nclass Solution {\n    public int smallestRepunitDivByK(int K) {\n        if(K%2 ==0 || K % 5 == 0){\n            return -1;\n        } else {\n            int remainder = 0;\n            for(int length = 1; length <= K; length++){\n                remainder = (remainder*10 + 1) % K;\n                if(remainder == 0)\n                    return length;\n            }\n        }\n        return -1;\n    }\n}\n```\n**PROBLEM OVERVIEW**\nWe are given a number whose digits only contain `1`. We are also given a divisor K, and need to find the length of the "N" (basically how many digits) until it is divisible by K.\n\n**SOLUTION ASSESSMENT**\nSince the digit ends in a 1:\n* Any even number is impossible because any mulitple of an even number is even (!=1)\n* 5 is impossible because all final digits of any multiple of 5 are 0 or 5.\n\nGreat! We cut the number of possibilities by 60%.\n\nNext, we may notice that for every increase of 1, 11, 111, ...,etc, the pattern may be modeled by\n* (current* 10) + 1\n* However, there is a warning that there may be `overflow,` even with a 64-bit signed number\n\nSo how can we work our way around this?\n\nWe can use the modulo operator and divide the number everytime there is a chance to. By doing so, we are essentially doing **long-division with the digits that we have, and the modulo operator does the task of "carrying over" the remainder.**\n\nSee *Quotient Remainder Theorem* [https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-quotient-remainder-theorem]\n\n**WORKED EXAMPLE**\nGIven K=3\n1. remainder = (0 + 1) % 3 = 1\n2. remainder = (10 * 1 + 1) % 3 = 2\n3. remainder = (2 * 1  + 1) % 3 = 0\n4. since remainder == 0, and it took 3 steps, the length = 3\n\nNow, here\'s the pigeonhole algorithm part. As we iterate from N = 1,11,111,..., etc, we are increasing the length by 1 each time. However, we **cannot have a length longer than K**. As we iterate from length 1 -> K, we have all the possible lengths; the pigeonhole principle asserts that there are at most K unique remainders. So if we iterate beyond K times, it is guaranteed that the remainder repeats, and there is not need to coninue searching.\n\n**TIME COMPLEXITY**\nO(N) - Iterates at most from 1->K. Note: K iterations is worst case.\n**SPACE COMPLEXITY**\nO(1) \n\n
['Java']