✅ [C++/Java/Python] 5 lines || Image Explain || Beginner Friendly
PLEASE UPVOTE if you like \uD83D\uDE01 If you have any question, feel free to ask. \n Inspired by the Theorem\n\t A fraction is either a finite decimal or an in
**PLEASE UPVOTE if you like** \uD83D\uDE01 **If you have any question, feel free to ask.** \n* Inspired by the Theorem\n\t* A fraction is either a finite decimal or an infinite loop decimal\n\t\t* 3 / 5 = 0.6\n\t\t* 2 / 7. = 0.**285714** 285714 2857...\n\t* Furthermore the length of the loop does not exceed the denominator.\n\t\t* because 0 <= remainder < denominator\n* Different from appending 0 to continue dividing when the fraction has a remainder, we append 1. But the state transition of remainder and divisor is similar.\n\t* **once the remainder repeats, in other word the loop starts that means it cannot be divisible**.\n* `if k % 2 == 0 or k % 5 == 0: return -1` trick can save a little time\n* when we code, we can either stop at repeated remainder or stop after k transfers.\n\t* stop at repeated remainder, we need to record the previous remainders, so the Space Complexity is O(k), but can save a little time\n\t* stop after k transfers, we can reduce the **Space Complexity to O(1)**\n\t* **Time Complexity** of both solutions above is **O(k)**, because 0 <= remainder < k, according to the **Pigeonhole Theorem**\n\t\n* It may be better to understand this problem from the perspective of state transition\n\t* we directly define the remainder as the state\n\t* The stop condition is that the remainder is 0, so 0 is the stop state.\n\t* `k = 7` can stop after 6 transfers, so we `return 6`\n\n\t\t![image](https://assets.leetcode.com/users/images/d46764d8-3bc1-48a2-b469-b4ad53ac92b1_1640853354.400817.jpeg)\n\n\t* `k = 12` enters the loop and won\'t stop, so we `return -1`\n\n\t\t![image](https://assets.leetcode.com/users/images/4c6051a6-98e7-46c1-b034-98e458cf97f4_1640853820.291282.jpeg)\n\n\n```\nTime  Complexity:O(k)\nSpace Complexity:O(k)\n```\n\n**Python**\n```\nclass Solution(object):\n    def smallestRepunitDivByK(self, k):\n        # if k % 2 == 0 or k % 5 == 0: return -1  # this trick may save a little time\n        hit, n, ans = [False] * k, 0, 0\n        while True:  # at most k times, because 0 <= remainder < k\n            ans, n = ans + 1, (n * 10 + 1) % k  # we only focus on whether to divide, so we only need to keep the remainder.\n            if n == 0: return ans  # can be divisible\n            if hit[n]: return -1  # the remainder of the division repeats, so it starts to loop that means it cannot be divisible.\n            hit[n] = True\n```\n**C++**\n```\nclass Solution {\npublic:\n    int smallestRepunitDivByK(int k) {\n        // if (k % 2 == 0 || k % 5 == 0) return -1;  // this trick may save a little time\n        int n = 0, ans = 0;\n        bool *hit = new bool[k];     \n        for (int i = 0; i < k; i ++) hit[i] = false;\n        while (true) { // at most k times, because 0 <= remainder < k\n            ++ ans;\n            n = (n * 10 + 1) % k; // we only focus on whether to divide, so we only need to keep the remainder.\n            if (n == 0) return ans; // can be divisible\n            if (hit[n]) return -1; // the remainder of the division repeats, so it starts to loop that means it cannot be divisible.\n            hit[n] = true;\n        }\n    }\n};\n```\n**Java**\n```\nclass Solution {\n    public int smallestRepunitDivByK(int k) {\n        // if (k % 2 == 0 || k % 5 == 0) return -1;  // this trick may save a little time\n        boolean[] hit = new boolean[k];\n        int n = 0, ans = 0;\n        while (true) { // at most k times, because 0 <= remainder < k\n            ++ ans;\n            n = (n * 10 + 1) % k; // we only focus on whether to divide, so we only need to keep the remainder.\n            if (n == 0) return ans; // can be divisible\n            if (hit[n]) return -1; // the remainder of the division repeats, so it starts to loop that means it cannot be divisible.\n            hit[n] = true;\n        }\n    }\n}\n```\n\n\n```\nTime  Complexity:O(k)\nSpace Complexity:O(1)\n```\n\n**Python**\n```\nclass Solution(object):\n    def smallestRepunitDivByK(self, k):\n        # if k % 2 == 0 or k % 5 == 0: return -1  # this trick may save a little time\n        n = 0\n        for i in range(k):  # at most k times, because 0 <= remainder < k\n            n = (n * 10 + 1) % k  # we only focus on whether to divide, so we only need to keep the remainder.\n            if n == 0: return i + 1  # i started from 0, so before return it should be added 1\n        return -1  # If it had not stop after k transfers, it must enter the loop, and it won\'t stop.\n```\n**C++**\n```\nclass Solution {\npublic:\n    int smallestRepunitDivByK(int k) {\n\t\t// if (k % 2 == 0 || k % 5 == 0) return -1;  // this trick may save a little time\n        int n = 0;\n        for (int i = 0; i < k; i++) { // at most k times, because 0 <= remainder < k\n            n = (n * 10 + 1) % k; // we only focus on whether to divide, so we only need to keep the remainder.\n            if (n == 0) return i + 1; // i started from 0, so before return it should be added 1\n        }\n        return -1; // If it had not stop after k transfers, it must enter the loop, and it won\'t stop.\n    }\n};\n```\n**Java**\n```\nclass Solution {\n    public int smallestRepunitDivByK(int k) {\n\t\t// if (k % 2 == 0 || k % 5 == 0) return -1;  // this trick may save a little time\n        int n = 0;\n        for (int i = 0; i < k; i ++) { // at most k times, because 0 <= remainder < k\n            n = (n * 10 + 1) % k; // we only focus on whether to divide, so we only need to keep the remainder.\n            if (n == 0) return i + 1; // i started from 0, so before return it should be added 1\n        }\n        return -1; // If it had not stop after k transfers, it must enter the loop, and it won\'t stop.\n    }\n}\n```\n\n**PLEASE UPVOTE if you like** \uD83D\uDE01 **If you have any question, feel free to ask.**
['C', 'Python', 'Java']