C++ | Digit DP | Simplest Solution | Clean Code
Intuition & Approach\nRather than finding numbers having repetitions, we can find: Total numbers - Numbers with all digits unique.\nMaintain a bitmask to make s
# Intuition & Approach\nRather than finding numbers having repetitions, we can find: `Total numbers - Numbers with all digits unique`.\nMaintain a bitmask to make sure that we don\'t re-select a digit which has already been included.\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[11][2][1025]; // 1025 -> (1 << 10)\n    int dfs(int i, int mask, bool tight, string &digits) {\n        if(i == digits.size()) {\n            return mask == 0 ? 0 : 1;\n        }\n\n        if(dp[i][tight][mask] != -1) return dp[i][tight][mask];\n\n        int limit = 9, res = 0;\n        if(tight) limit = (digits[i] - \'0\');\n\n        for(int dig = 0; dig <= limit; dig++) {\n            // mask = 0 -> No number has been formed yet &\n            // dig = 0 -> We can\'t select first digit as 0 \n            if(mask == 0 && dig == 0) {\n                res += dfs(i + 1, mask, (tight & (limit == dig)), digits);\n                continue;\n            }\n            // Check if the current digit has already been included\n            int repeated = mask & (1 << dig);\n            // If it hasn\'t, include it and furthur proceed\n            if(repeated == 0) {\n                res += dfs(i + 1, mask | (1 << dig), (tight & (limit == dig)), digits);\n            }\n        }\n\n        return dp[i][tight][mask] = res;\n    }\n    int numDupDigitsAtMostN(int n) {\n        memset(dp, -1, sizeof dp);\n        string x = to_string(n);\n        return n - dfs(0, 0, true, x);\n    }\n};\n```
['Dynamic Programming', 'C++']