Beats 100% (0ms) | Java | Combinatorial solution and explanation without digit dp/recursion
Intuition\nRather than computing how many numbers in a range have a repeated digit,  it may be easired to compute how many numbers have no repeated digits and t
# Intuition\nRather than computing how many numbers in a range have a repeated digit,  it may be easired to compute how many numbers have no repeated digits and then subtract that from the total number of numbers in the range. \nThe problem then is reduced to finding a fast way to enumerate non-repeating numbers in a range. \n\n# Approach\nWe are given a number $n$. If it is no more than $10$, there are obviously no numbers with repeating digits less than or equal to it, so we return zero. Otherwise, we extract the digits, and proceed from there. Suppose that $n$ is represented by digits $d_kd_{k-1}\\dots d_1d_0$. \n\nNow, read from left to right along a number. Replace $d_i$ with the count of numbers in the range $[0, d_i]$ that have not already occured. (If a number occurs twice, then we set every digit to the right of it to zero). Call this new sequence of adjusted digits $a_i$. \n\nWe then calculate the following values ($E$ and $F$ are the variables `partial` and `full`)\n$$\n\\begin{align}\nE & = 9P(9,0) + 9P(9,1) + \\cdots+ 9P(9,k-1)\\\\\nF & = (a_k - 1)P(9,k) + a_{k-1}P(8,k-1) + \\cdots + a_1P(9-k+1,1)+a_0P(9-k,0)\n\\end{align}\n$$\nWhere $P(n,k) = \\frac{n!}{(n-k)!}$.  \n\n$E$ is the number of non-repeating positive integers that have fewer digits than $n$, while $F$ is the number of non-repeating positive integers that have the same number of digits as $n$, but are less than $n$. Together $E + F$ give the number of positive integers without repeating digits that are less than $n$. So, depending on if $n$ itself repeats, the number of positive integers with repeating digits in the range $1$ through $n$ is either $n - (E + F)$ or $n - (E + F + 1)$. \nThis is what the final for-loop calculates, except that we take advantage of the fact that $P(n + 1,k +1) = (n+1)P(n,k)$ to reduce the need to calculate all of the factorials. \n\nThe formula for $E$ comes from considering how many ways a non-repeating number can be made out of a given number of digits. There are 9 non-repeating 1-digit numbers, 81 2-digit, 648 3-digit amd so on. The pattern is that, in general, there are $9$ options for the first digit, being 1-9. Then, 9 options for the second digit, because while the first may not be used again, it is possible to use zero. There are 8 options for the third (to avoid reusing the digit from the first or second space), then 7,6,5 etc. Each term of $E$ corresponds to a different number of digits.\n\nThe formula for $F$ is a bit less obvious. Each term gives the number of non-repeating numbers which differ from $n$ in a given digit. The $a_0$ term gives those which agree in all places except the very right digit, while the $a_k$ term counts up how many ways a non-repeating number can be made whose first digit range from $1$ to 1 less than the starting digit of $n$, and those in between count how the in-between digits may be varied.\n\n \n\n# Code\n```\nclass Solution {\n    public int numDupDigitsAtMostN(int n) {\n        if (n < 11)\n        {\n            return 0;\n        }\n\n        //extract the digits\n        int digits[] = new int[10];\n        int tempN = n; \n        int digitCount = 0;\n        while (tempN > 0)\n        {\n            digits[digitCount] = tempN % 10;\n            tempN /= 10;\n            digitCount++;\n        }\n\n        //Using those digits, calculate the adjusted digits: suppose the prefix is maximized, how many \n        //digits may fill this \'slot\'\n        boolean occ[] = new boolean[10];\n        boolean zeroRest = false;\n        for (int i = digitCount-1; i >= 0; i--)\n        {\n            if (zeroRest)\n            {\n                digits[i] = 0;\n                continue;\n            }\n\n            int digit = digits[i];\n            int adjusted = digit;\n            for (int j = 0; j < digit; j++)\n            {\n                if (occ[j])\n                {\n                    adjusted -= 1;\n                }\n            }\n            \n            //if this is a repeat\n            if (occ[digit])\n            {\n                zeroRest = true;\n            }\n\n            digits[i] = adjusted;\n            occ[digit] = true; \n        }\n\n        if (!zeroRest)\n        {\n            digits[0]++;\n        }\n\n\n        int full = 0; \n        int partial = 0;\n\n        int suffixCount = 1;\n        int partialSuffixCount = 1;\n        for (int i = 0; i < digitCount - 1; i++)\n        {\n            full += digits[i] * suffixCount;\n            suffixCount *= (11 - digitCount + i);\n\n            partial += 9 * partialSuffixCount;\n            partialSuffixCount *= (9 - i);\n\n        }\n        full += (digits[digitCount-1]-1)*suffixCount;\n\n        return n - full - partial;\n\n    }\n}\n```\n\n![image.png](https://assets.leetcode.com/users/images/1258c480-c240-48ca-93d9-4a57478969ae_1721711264.4046032.png)\n\n\n
['Math', 'Combinatorics', 'Java']