[Java/Python] Count the Number Without Repeated Digit
Intuition\nCount res the Number Without Repeated Digit\nThen the number with repeated digits = N - res\n\nSimilar as\n788. Rotated Digits\n902. Numbers At Most 
# **Intuition**\nCount `res` the Number Without Repeated Digit\nThen the number with repeated digits = N - res\n\nSimilar as\n788. Rotated Digits\n902. Numbers At Most N Given Digit Set\n\n\n# **Explanation**:\n\n1. Transform `N + 1` to arrayList\n2. Count the number with digits < n\n3. Count the number with same prefix\n\nFor example,\nif `N = 8765`, `L = [8,7,6,6]`,\nthe number without repeated digit can the the following format:\n`XXX`\n`XX`\n`X`\n`1XXX ~ 7XXX`\n`80XX ~ 86XX`\n`870X ~ 875X`\n`8760 ~ 8765`\n\n\n# **Time Complexity**:\nthe number of permutations `A(m,n)` is `O(1)`\nWe count digit by digit, so it\'s `O(logN)`\n\n<br>\n\n**Java:**\n```java\n    public int numDupDigitsAtMostN(int N) {\n        // Transform N + 1 to arrayList\n        ArrayList<Integer> L = new ArrayList<Integer>();\n        for (int x = N + 1; x > 0; x /= 10)\n            L.add(0, x % 10);\n\n        // Count the number with digits < N\n        int res = 0, n = L.size();\n        for (int i = 1; i < n; ++i)\n            res += 9 * A(9, i - 1);\n\n        // Count the number with same prefix\n        HashSet<Integer> seen = new HashSet<>();\n        for (int i = 0; i < n; ++i) {\n            for (int j = i > 0 ? 0 : 1; j < L.get(i); ++j)\n                if (!seen.contains(j))\n                    res += A(9 - i, n - i - 1);\n            if (seen.contains(L.get(i))) break;\n            seen.add(L.get(i));\n        }\n        return N - res;\n    }\n\n\n    public int A(int m, int n) {\n        return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);\n    }\n```\n**Python3**\n```py\n    def numDupDigitsAtMostN(self, N):\n        L = list(map(int, str(N + 1)))\n        n = len(L)\n        res = sum(9 * perm(9, i) for i in range(n - 1))\n        s = set()\n        for i, x in enumerate(L):\n            for y in range(i == 0, x):\n                if y not in s:\n                    res += perm(9 - i, n - i - 1)\n            if x in s: break\n            s.add(x)\n        return N - res\n```\n
['Python', 'Java']