**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.**

Smallest Integer Divisible by K

Problem Description

Problem Description

Answer Panel