C++ with Alternative Explanation
Really enjoyed working through this problem and pushing myself to better understand permutations because of it, and figured I\'d post my explanation of this pro
Really enjoyed working through this problem and pushing myself to better understand permutations because of it, and figured I\'d post my explanation of this problem here. The basic idea behind this problem is to instead determine how many **invalid** numbers exist from **1-N**, rather than trying to find the valid numbers.\n\nTo do this, we can make heavy use of the permutations formula (see [here](https://www.mathplanet.com/education/algebra-2/discrete-mathematics-and-probability/permutations-and-combinations) for a great explination on it) since it gives us the number permutations of unique numbers. We can start by figure out how many digits are in our number, and varying all of the digits in L-1 (L being the number of digits).\n\nFor example, with the number 350, we have 3 digits, meaning we can start by finding all **invalid** numbers from 0 to 99 (e.g. the first two digits). To start, let\'s assuming we only have 1 digit available. In this case, we can\'t vary any other digits in the number since there are none, and because there is only 1 digit they are all invalid. Thus, since there are 9 total numbers with 1 digit, we have 9 invalid permutations for this digit. Similarly, for 2 digits, we have 1 digit we can vary (e.g. 1x has x that can be varied, 2y has y that can be varied, so on and so forth). Plugging that into our our formula, we have perm(9, 1) which results in 9. Because there are 9 possible digits for the first digit, we can multiply the result by 9 (perm(9, 1) * 9) which gives us 81 invalid digits. Adding that onto our first result of 9, and we get 90 invalid digits for a number range of 1-99 (meaning we have 9 valid digits in that range).\n\nAt this point, for the number 350, we know that thare are at least 90 invalid digits from 1-100 as a result (since 100 is valid). Now however we need to count the number of invalid digits from 100-350. This can be done by varying each of the digits in 351 (e.g. N+1), and finding the valid permutations of that as a result. For example:\n```\n3XX -> perm(9-0, 3-0-1) -> perm(9, 2)\nX5X -> perm(9-1, 3-1-1) -> perm(8, 1)\nXX1 -> perm(9-2, 3-2-1) -> perm(7, 0)\n```\nWe then add this number of invalid permutations to our count based on the number we have. However, if we\'ve previously seen a number in that range, we ignore it. For example, when we get to the 5 in 351, we will only add perm(8, 1)\'s result 4 times, since the third time has already been accounted for when we went over the 3 in 351. Once we\'ve done all of this, we can simply subtract our number of invalid numbers from our original number N to get our result.\n\nHere is what this process looks like in action:\n```\n350 -> 351\ninvalid digits -> 0\n\n1 digit -> X -> perm(9, 0) * 9 -> 9 invalid digits\n2 digits -> YX -> perm(9, 1) * 9 -> 81 invalid digits\ninvalid digits -> 90\n\n0XX -> invalid so don\'t count the invalid digits.\n1XX -> perm(9, 2) -> 72 invalid digits\n2XX -> perm(9, 2) -> 72 invalid digits\n3XX -> stop counting invalid numbers for the first digit.\nX0X -> perm(8, 1) -> 8 invalid digits\nX1X -> perm(8, 1) -> 8 invalid digits\nX2X -> perm(8, 1) -> 8 invalid digits\nX3X -> perm(8, 1) -> 8 invalid digits -> but because we\'ve already looked at the digit 3 previously we can skip this.\nX4X -> perm(8, 1) -> 8 invalid digits\nX5X -> stop counting invalid numbers for the second digit.\nXX0 -> perm(7, 0) -> 1 invalid digit\nXX1 -> stop counting invalid numbers for the third and final digit.\ninvalid digits -> 267\n\nresult -> 350 - 267 = 83\n```\nAnd the full code looks like this:\n```\nclass Solution {\npublic:\n    int numDupDigitsAtMostN(int N) {\n        int invalid = 0;\n        \n        // Begin by calculating all of the invalid numbers up to 10^(L-1), where L is the length of our number (e.g. For 350, we would find all invalid numbers between 1 and 99)\n        int c = floor(log10(N+1))+1;\n        for (int i = 0;i < c-1;i++) {\n            invalid += 9 * perm(9, i);\n        }\n\n        // For each digit, calculate the possible invalid permutations that are available up until that digit.\n        int digits = 0;\n        for (int i = 0;i < c;i++) {\n            // Get the left most digit.\n            int digit = ((N+1) / (int)pow(10, c-i-1)) % 10;\n            // Count up to the digit. Note that if it\'s the first digit, we start at 1 to avoid finding permutations when the first digit is a 1 since there are none.\n            for (int j = (i > 0 ? 0 : 1);j < digit;j++) {\n                // If we\'ve had the same digit to the left of it previously, then we don\'t need to count it again.\n                // E.g. If our number is 350, when get to 330-339 we\'ve already considered all possible invalid permutations for that number range and can skip it.\n                if (((digits >> j) & 1) == 0) {\n                    invalid += perm(9 - i, c - i - 1);\n                }\n            }\n            // If we end up finding a digit we\'ve already searched, we can finish here.\n            if ((digits >> digit) & 1)\n                break;\n            digits |= 1 << digit;\n        }\n\n        return N - invalid;\n    }\n    \n    int perm(int m, int n) {\n        int out = 1;\n        while (m > 1 && n > 0) {\n            out *= m;\n            m--;\n            n--;\n        }\n        return out;\n    }\n};\n```\nSome trickery I used: **log10(N+1) + 1** counts the number of digits we have for us so we don\'t have to do another loop over them. We can then also abuse some other mathematics to quickly iterate over this without any additional memory, resulting in a **O(c) memory usage, where c is a constant value (e.g. O(1))**. The runtime of this is going to be **O(L\xB2) where L is the number of digits** from what I can tell, because our second for loop will iterate over every digital (with a max of 9 being possible), and for each digit will iterate over the range of numbers from 0 to D (D being the digit we are on) which also has a mximum possible value of 9. **My math on the runtime may be off, so please correct me if that\'s the case, as I would like to know the correct runtime.**\n\nAs far as further optimizations on the runtime, I\'m not sure how possible this is since we ultimately need to make sure we don\'t double count any of the previously checked digits. Feedback on this explination would be greatly appreciated as well!
['C++']