C++ EASY TO SOLVE || Everything you need to Know from Intuitions till Proofs
Everything you need to Know from all the Intuitions till Proofs\n>  At start let\'s reframe the question for better understanding .\nSo the question is we are g
# **Everything you need to Know from all the Intuitions till Proofs**\n>  **At start let\'s reframe the question for better understanding .**\nSo the question is we are given a number `K` , check every `N` until the solution is found or no solution exists.\nWe can start N with the first one that is greater than or equal to K.\nSo in simple words we need to find a integer `N` where `N` can be 1 , 11, 111, 1111, 1111....1 and we can say `N` is a integer which is made up of 1\'s and `K` is the input number that should divide `N`\n***\n**For example:-**\n```\nInput: k = 3 \nSo N can be:\n1   ->1/3    N is not divisible by K\n11 ->11/3    N is not divisible by K\n111->111/3   N is divisble by k\nso the answer is the length of  N(111) i.e  3\nOutput: 3\t\t\t\n```\n***\n\n**1st Intuition:-**\nAfter understanding the question one thing is clear that at every iteration we need to append 1 to the previous `N` i.e <mark>1 =append 1->11  =append 1-> 111  =append 1->1111....</mark> and this goes on till we get a `N` which is divisble by `K` .\n***\n**2nd Intuition:-**\nAfter some brainstorming and getting bald by finding this intuition :) I got this 2nd intuition that if we need to append a digit to a number by 1 digit, the easiest way is to multiply it by 10 .Let me explain this in a more clear way.\n```\nso let\'s say you have a number 123 \nThe number of digits it has is 3\nNow if we multiply it by 10 =>123 * 10 = 1230\nyup, we successfully added a digit easily by multiplying it by 10 so now the total number of digits are 4 .\n```\nThe above intuition will help us to get the N as 1 ,11 ,111 ,1111 .... \nFinally some joy, as we are getting close to result.\n***\n**3rd Intuition :-**\n* Now the question arises that we can add a 0 easily at the end to increase the number of digits but how to add a specific digit at end (in our case instead of 0\'s we need 1\'s) !???\nOkkk , so let\'s take the same number 123 . let\'s say this time we want to append a digit 2 instead of 0 .\n\n<mark>An observation we all know:-If we are appending a single digit to a number it increases the value of the last digit of the original number by the same amount\n123[N] +2[single digit] = 125 [final number]\nso we can see that in N we addded a digit 2 and the final number is incremented by 2\n</mark>\n***\n**4th Intuition:-**\n* Now let\'s see how can we conclude the answer for how to append a specific digit at end (in our case instead of 0\'s we need 1\'s) !???\n* **So in conclusion,** to append a specific digit at the end of a number, we first multiply it by 10 (freeing up the last digit slot) and then add the digit that we want to append.\n\n**Let\'s take a example:-**\n```\nLet\'s say we want to append 2 at the end of 123\n\nn*10 = 1230(slot freed)\nn*10 + 2 = 1232 (Number 2 appended).\nNot gonna lie that was cool :)\n```\n***\n**Final Intution:-**\n* After understanding the above 4 intuitons we\'ve understood now how to append a digit at the end of a number. Let us see how can we generate the sequence 1, 11, 111, ....111...11 using the above Intuitions.\n\n**So now we need to append 1\'s as we increment our sequence**\n\nSo, Let\'s start out with num = 1 and repeatedly do num = num * 10 + 1, then in every iteration we\'ll get a new number with a digit 1 appended and in the end we will get the above sequence.\n\n1 * 10 + 1 = 11\n11 * 10 + 1 = 111\n111 * 10 + 1 = 1111\n1111 * 10 + 1 = 11111\n11111 * 10 + 1 = 111111\n1111111 * 10 +1 =1111111\n***\n**The rise of a new issue :(**\n* We can get the remainder directly from N by N % K and move on to the next N by N = N * 10 + 1.\nBut but there is a issue when N will soon be overflow since max integer in cpp/java is +2,147,483,647, which means the max N is 1,111,111,111 .\n* So instead of creating whole new numbers every time we will just use the remainder of the next N with the previous reminder\n\n**So how do we do it ????**\nBy the rules of modular arithmetic (a * b + c) mod m  is same as ((a * b) % m + c % m) % m.THINK!!!\n\n**Let\'s see the proof of the above statement:-**\n```\nHere is a rule to get the remainder of the next N with the previous remainder.\nN = m * k + r ......*where r is n % k and m is modulo*\n10 * N + 1 = 10 * (m * k + r) + 1\n10 * N+ 1 = 10 * m * k + 10 * r + 1\n(10 * N + 1) % k = (10 * m * k + 10 * r + 1) % k\n(10 * N + 1) % k = (10 * r + 1) % k // (10 * m * k) % k = 0\n```\nSo whatever N is, (10 * n + 1) % k equals to (10 * r + 1) % k, where r is n % k. So that\'s why we only need to keep the remainder and thus the issue get\'s resolved .\n***\n\n*This was tough not gonna lie, now i can die happily :))*\n**Code:-**\n```\nclass Solution {\npublic: \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\n**Time Complexity:-** `O(K) `\n**Space Complexity:-** `O(1)`\n\n***
['Math', 'C', 'C++']