Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nDigit dp. Try to find the numbers without repeated digits from 1 to N. Then subtract 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nDigit dp. Try to find the numbers without repeated digits from 1 to N. Then subtract this from N.\n\n1. DP form: knapsack. We pick from what digit we want at what position. We decide the num1 and num2 between which we calculate beforehand.\n2. DP meaning: dp(i, state, tight1, tight2) = number of numbers without repeated digits from i..n given state is the bitmask where set bit means the digit has already been used and tight1, tight2 are bools which indicate whether the digits so far are exactly those used in num1 and num2 respectively.\n3. DP transition: dp(i, state, tight1, tight2) -> dp(i+1, (1<<d)|state, tight1&&(d==num1[i]), tight2&&(d==num2[i])). For handling leading zeros we can have an extra boolean in the recurrence so that we don\'t set any bit 0 till we actually use 0 inside a number and not as a leading zero.\n4. TC: O(log(n)) as we depend on the number of digits in n\n5. Set the inital values of num1 and num2 to 00..001 and num2 = n respectively such that both have the same length. We can generalize this to any n1 and n2 as well.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[10][1024][2][2];\n    int n;\n    string num1;\n    string num2;\n\n\n    int rec(int i, int state, bool tight1, bool tight2, bool leading_zeros)\n    {\n        if(i == n)\n        {\n            return 1;\n        }\n\n        if(dp[i][state][tight1][tight2] != -1)\n        {\n            return dp[i][state][tight1][tight2];\n        }\n\n        int ans = 0;\n\n        int lower_bound = tight1 ? (num1[i] - \'0\') : 0;\n        int upper_bound = tight2 ? (num2[i] - \'0\') : 9;\n\n        for(int d = lower_bound; d<=upper_bound; d++)\n        {\n\n            if(d == 0 && leading_zeros)\n            {\n                ans = (ans + rec(i+1, state, tight1 && (d == lower_bound), tight2 && (d == upper_bound), leading_zeros));\n            }\n            else\n            {\n                int bit = (1 << d);\n\n                if((bit & state) == 0)\n                {\n                    ans = (ans + rec(i+1, bit|state, tight1 && (d == lower_bound), tight2 && (d == upper_bound), false));\n                }\n            }\n        }\n\n        return dp[i][state][tight1][tight2] = ans;\n    }\n\n    int numDupDigitsAtMostN(int n) {\n        memset(dp, -1, sizeof(dp));\n        this->num2 = to_string(n);\n        this->num1 = string((this->num2).size() - 1, \'0\') + "1";\n        this->n = (this->num2).size();\n        rec(0, 0, true, true, true);\n        return n - dp[0][0][1][1]; // replace this line with n2 - n1 + 1 - dp[0][0][1][1] for general n1, n2\n    }\n};\n```
['C++']