Digit Dp Soln
class Solution {\npublic:\n    string num;\n    int l ;\n    int dp[11][2][2][1030];\n    \n    int d(int N)\n    {\n        int c = 0;\n        while(N)\n     
class Solution {\npublic:\n    string num;\n    int l ;\n    int dp[11][2][2][1030];\n    \n    int d(int N)\n    {\n        int c = 0;\n        while(N)\n        {\n            c++;\n            N /= 10;\n        }\n        return c;\n    }\n    \n    int solve(int bit, int tight, int nonz, int mask)\n    {\n        if(dp[bit][tight][nonz][mask] != -1)\n            return dp[bit][tight][nonz][mask];\n        \n        if(bit == l)\n        {\n            if(nonz)\n                return dp[bit][tight][nonz][mask] = 1;\n            else\n                return dp[bit][tight][nonz][mask] = 0;\n        }\n        \n        int v = num[bit] - \'0\';\n        //cout << v << \'\\n\';\n        int cans = 0;\n        if(tight)\n        {\n            for(int i = 0; i <= v; i++)\n            {\n                int new_mask = mask;\n                int new_tight = 0;\n                int c_bit = ((mask >> i) & 1);\n                if(nonz || (i != 0))\n                    new_mask |= (1 << i);\n                if(i == v)\n                    new_tight = 1;\n                if(c_bit == 0)\n                    cans += solve(bit + 1, new_tight, nonz || (i != 0),new_mask);\n            }\n        }\n        else\n        {\n            for(int i = 0; i <= 9; i++)\n            {\n                int new_mask = mask;\n                int c_bit = ((mask >> i) & 1);\n                if(nonz || (i != 0))\n                    new_mask |= (1 << i);\n                if(c_bit == 0)\n                    cans += solve(bit + 1, 0, nonz || (i != 0), new_mask);\n            }\n        }\n        return dp[bit][tight][nonz][mask] = cans;\n    }\n    int numDupDigitsAtMostN(int N) {\n        int dig = d(N);\n        num = to_string(N);\n        l = num.size();\n        memset(dp, -1, sizeof dp);\n        return (N - solve(0,1,0,0));\n    }\n};
[]