[Java/C++/Python] O(1) Space with Proves of Pigeon Holes
Intuition:\nLet\'s say the final result has N digits of 1. \nIf N exist, N <= K, just do a brute force check.\nAlso if K % 2 == 0, return -1, because 111....11 
## **Intuition**:\nLet\'s say the final result has `N` digits of 1. \nIf `N` exist, `N <= K`, just do a brute force check.\nAlso if `K % 2 == 0`, return -1, because 111....11 can\'t be even.\nAlso if `K % 5 == 0`, return -1, because 111....11 can\'t end with 0 or 5.\n<br>\n\n\n## **Explanation**\nFor different `N`, we calculate the remainder of mod `K`.\nIt has to use the remainder for these two reason:\n\n1. Integer overflow\n2. The division operation for big integers, is **NOT** `O(1)`, it\'s actually depends on the number of digits..\n\n\n## **Prove**\n\nWhy 5 is a corner case? It has a reason and we can find it.\nAssume that `N = 1` to `N = K`, if there isn\'t `111...11 % K == 0`\nThere are at most `K - 1` different remainders: `1, 2, .... K - 1`.\n\nSo this is a pigeon holes problem:\nThere must be at least 2 same remainders.\n\n\nAssume that,\n`f(N) \u2261 f(M)`, `N > M`\n`f(N - M) * 10 ^ M \u2261 0`\n`10 ^ M \u2261 0, mod K`\nso that K has factor 2 or factor 5.\n\n\nProof by contradiction\uFF0C\n`If (K % 2 == 0 || K % 5 == 0) return -1;`\notherwise, there must be a solution `N <= K`.\n\n## **Time Complexity**:\nTime `O(K)`, Space `O(1)`\n\n<br>\n\n**Java:**\n```\n    public int smallestRepunitDivByK(int K) {\n        if (K % 2 == 0 || K % 5 == 0) return -1;\n        int r = 0;\n        for (int N = 1; N <= K; ++N) {\n            r = (r * 10 + 1) % K;\n            if (r == 0) return N;\n        }\n        return -1;\n    }\n```\n\n**C++:**\n```\n    int smallestRepunitDivByK(int K) {\n        for (int r = 0, N = 1; N <= K; ++N)\n            if ((r = (r * 10 + 1) % K) == 0)\n                return N;\n        return -1;\n    }\n```\n\n**Python:**\n```\n    def smallestRepunitDivByK(self, K):\n        if K % 2 == 0 or K % 5 == 0: return -1\n        r = 0\n        for N in xrange(1, K + 1):\n            r = (r * 10 + 1) % K\n            if not r: return N\n```\n
[]