[C++] Simple Short Explanation | No Pigeon Holes
Explanation - \n\nSince the series is 1, 11, 111, 1111, ... so the Next_Num = Prev10+1;\n\nNow using some modulo property.\nLet say remainder from prev is - \nA
Explanation - \n\nSince the series is 1, 11, 111, 1111, ... so the Next_Num = Prev*10+1;\n\nNow using some modulo property.\nLet say remainder from prev is - \nA = Prev%K;\nB = Next%K \n= (Prev * 10 + 1)%K \n= ( (Prev * 10)%K + 1%K )%K\n= ( ( (Prev%K) * (10%K) )%K + 1%K )%K \n=( ( A * (10%K) )%K + 1%K )%K\n=( ( A * 10 )%K + 1%K )%K\n=(A*10+1)%K    --- Equation #1\n\nAlso to note that if we reach a remainder(X) which we have already seen, then same steps will be repeated and we will again reach X if we proceed ahead. This means we will never reach remainder = 0 and move infinitely in cycle. So keep track of what all remainder we have seen so far in set or array, whichever way you prefer.\n```\nclass Solution {\npublic:\n    int smallestRepunitDivByK(int K) {\n        unordered_set<int>st;     // to keep track of remainders we have seen so far\n        int rem=1%K;                  // Series start with 1\n        while(rem!=0 && st.find(rem)==st.end()){\n            st.insert(rem);\n            rem=(rem*10+1)%K;     // From Equation #1 above\n        }\n        \n        if(rem==0)\n            return st.size()+1;        // Set has all the intermediate remainders we got before we reach zero, so answer is one more than size of set\n        \n        return -1;\n    }\n};\n```
['C']