C++ | digit dp
\nclass Solution {\npublic:\n    string num;\n    int len;\n    int setKthBit(int n, int k)\n    {\n        return ((1 << (k)) | n);\n    }\n    bool isKthBitSe
```\nclass Solution {\npublic:\n    string num;\n    int len;\n    int setKthBit(int n, int k)\n    {\n        return ((1 << (k)) | n);\n    }\n    bool isKthBitSet(int n, int k)\n    {\n        return ( n & (1 << k) );\n    }\n\n    // mask reprsents the set of numbers already in the number //\n    // like for 1,2,4  maks = 00000001011 // \n    // we can also use an explicit set but that will be difficult to cache and as we can have only 10 numbers that are 0-9 therefore only 2^11 will be used 2048   \n    int memo[12][2][5000][2];\n    // to find the count of numbers with unique digits //\n    int dp(int n, bool tight, int mask, bool leadingzero){\n        \n        // base case //\n        if(n==0){\n            int base = 0;\n            int ub = tight ? num[len-1-n]-\'0\' : 9;\n            for(int i=0; i<=ub; ++i){\n                if(!isKthBitSet(mask, i))\n                base += 1;\n            }   \n            return base;\n        }\n        \n        if(memo[n][tight][mask][leadingzero]!=-1)\n            return memo[n][tight][mask][leadingzero];\n        \n        // recc //\n        int res = 0;\n        int ub = tight ? num[len-1-n]-\'0\' : 9;\n       \n        \n        for(int i=0; i<=ub; ++i){\n            if(i==0){// for leading zero we wont set it in the mask // eg 00035 is actually unique but as there are 3 zeros leading it wont be unique therfore to handle these type of cases//\n                if(leadingzero)\n                res += dp(n-1, tight && i==ub, mask, leadingzero);\n                else{\n                    if(!isKthBitSet(mask, i))\n                    res += dp(n-1, tight && i==ub, setKthBit(mask, i), leadingzero);\n                }   \n                \n            }\n            else{\n                if(!isKthBitSet(mask, i)){\n                    res += dp(n-1, tight && i==ub, setKthBit(mask, i), false);\n                } \n            }\n        }\n        return memo[n][tight][mask][leadingzero] = res;\n    }\n    \n    int numDupDigitsAtMostN(int n) {\n        \n        memset(memo, -1, sizeof memo);\n        \n        num = to_string(n);\n        len = num.length();\n        \n        int ans = dp(len-1, true, 0, true);\n        \n        ans = n+1 - ans ; \n        \n        return ans;\n    }\n};\n```
['Dynamic Programming']