✅ [C++/Python] Simple Solution w/ Explanation | Brute+ Optimizations w/ Math & Pigeonhole
We are given an integer k and we need to find the length of smallest integer n which is divisible by k. Return -1 if no such n exists.\n\n----\n\n\u2714\uFE0F S
We are given an integer `k` and we need to find the length of smallest integer `n` which is divisible by `k`. Return -1 if no such `n` exists.\n\n----\n\n\u2714\uFE0F ***Solution - I (Brute-Force w/ some Math to avoid Overflow)***\n\nTo start, we can see that the problem can be divided into two cases -\n* **`n` exists such that `n % k == 0`**: \n\t* Starting with `n = 1`, we can simply keep appending 1 at its end till we dont get `n % k == 0`. \n\t* We are given that **`n` may not fit in 64-bit integers**. So simply looping till we dont get `n % k == 0`  may work in languages supporting big integers and maybe for other languages you can even maintain string & write custom division function for long integer string division, but it will be very inefficient.\n\t* Let remainder `R1 = n1 % k`. If `R1 != 0`, then the next `n2` after appending 1 would be `n1 * 10 + 1`. \n\t We then have: \n\t\t ```python\n\t\t =>  R2 = n2 % k \n\t\t =>  R2 = (n1 * 10 + 1) % k                        ... [ putting in value of n2 ]\n\t\t =>  R2 = [(n1 % k) * (10 % k)] % k + 1 % k        ... [ modulo property ]\n\t\t =>  R2 = [R1 * (10 % k)] % k + 1 % k              ... [ \u2235 R1 = n1 % k ]\n\t\t =>  R2 = (R1 * 10 + 1) % k\n\t\t ```\n\t* Thus, we can **use previous remainder `R`, append `1` to its end, then take its mod `k` and use it in the next iteration**. This avoids overflow and is more efficient than keep appending 1 at the end of `n` itself (doing `n % k` is not O(1) operation for big integers even in langauge that support it).\n\t* Finally at some point, we find `n % k == 0` at which point we will return the iteration count as the answer (since we were adding only 1 digit at each iteration).\n\n* **no such `n` exists**:\n\t* If no `n` exists such that `n % k == 0`, then we need to find a way to see it and not get caught in infinite loop\n\t* Since there\'s a **finite number of possible remainders** for a given input `k`, if no `n` exist, then the same remainder is bound to repeat again sometime.\n\t* Thus, if a remainder occurs again, we can directly `return -1` because in this case no `n` exist and we will just keep going in inifite loop.\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int smallestRepunitDivByK(int k) {\n        int n = 1, R;\n        unordered_set<int> seen;\n        for(int i = 1; ; i++) {\n            R = n % k;                      // find remainder\n            if(R == 0) return i;            // if R == 0, we found the required n, returns its length\n\t\t\tif(seen.count(R)) return -1;    // seen again? no n exists, so return -1\n            seen.insert(R);                 // mark as seen\n            n = R * 10 + 1;                 // update n for next iteration\n        }\n        return -1;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def smallestRepunitDivByK(self, k: int) -> int:\n        n, seen, i = 1, set(), 1\n        while True:\n            R = n % k\n            if R == 0: return i\n            if R in seen: return -1\n            seen.add(R)\n            n = R * 10 + 1\n            i += 1\n```\n\n***Time Complexity :*** `O(K)`, We keep iterating till we either find `n % k == 0` or a repeated remainder. In the worst case, we find all possible `k` remainder before returning final result which requires `O(k)` time\n***Space Complexity :*** `O(K)`, for storing `seen` remainders\n\n---\n\n\u2714\uFE0F ***Solution - II (Optimization w/ Math & Pigeonhole Principle)***\n\nWe can further optimize the solution by using the **[pigeonhole principle](https://en.wikipedia.org/wiki/Pigeonhole_principle)** which states that if there are `n` items to be placed in `m` places with `n > m`, then atleast one place must contain more than 1 item. In this case, we have `k` possible remainders from `0 to k-1`. So, when we try to place remainder `R` into `seen` for more than `k` times, we will definitely find a duplicate. Thus, we can optimize on space by simply iterating `k` times and if we dont find a `R == 0`, then we will return -1 at the end (since `R` must have or will repeat from that point).\n\nFurthermore, we can see that since `n` consists only of `1`s, the answer will never exist in the cases where `k` is divisible by `2` or `5`. This is because a number `n` ending with 1 can never be divisible by an integer `k` which is even (`k % 2 == 0`) or ending with 5 (`k % 5 == 0`).\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int smallestRepunitDivByK(int k) {\n        if(k % 2 == 0 or k % 5 == 0) return -1;\n        int n = 1, R;\n        for(int i = 1; i <= k ; i++) {\n            R = n % k;                      \n            if(R == 0) return i;              \n            n = R * 10 + 1;                \n        }\n        return -1;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def smallestRepunitDivByK(self, k: int) -> int:\n        if k % 2 == 0 or k % 5 == 0: return -1\n        n = 1\n        for i in range(k):\n            R = n % k\n            if R == 0: return i+1\n            n = R * 10 + 1\n```\n\n***Time Complexity :*** `O(K)`\n***Space Complexity :*** `O(1)`\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---\n
[]