BitMask DP || C++
Intuition\nFinding numbers with at least one repeated digits means finding numbers with all unique digits and subtracting it from n this will give us the digits
# Intuition\nFinding numbers with at least one repeated digits means finding numbers with all unique digits and subtracting it from $$n$$ this will give us the digits with at least one repeated digit in it.\nNow we Divide the problem into two parts in the first part we will calculate number of unique numbers in the range \n0-9 (1 digit)\n10-99 (2 digits)\n100-999 (3 digits)\n....... (number of digits in $$n$$ -1)\n(1 - x) in total\n\nThen in the second half we will find number of unique numbers in the range (x+1 to n).\n \n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFor the first half just make use of simple permutaion. Compute for every number of digits.\nIn the second half make use of BitMask.\nMake a dp array that will store the position we are currently in, is our current position/digit our max value i.e. we can go higher than it? and a mask that will store wether the number has been added or not. \n\n\nI\'m open to discussion of my code if you are stuck anywhere.\nJust leave a comment and I will reply within 1 hour max.\nPlease upvote if you find it useful. \n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(11 * 2 * 1024)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(11 * 2 * 1024)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nint dp[11][2][1024];\nclass Solution {\npublic:\n\n    int f(int position,bool isprefix,int mask,int n,string num){\n\n        if(position >= n) return 1;\n        if(dp[position][isprefix][mask] != -1) return dp[position][isprefix][mask];\n\n        int start = (position == 0)? 1 : 0;\n        int limit = isprefix ? (num[position] - \'0\') : 9;\n        int ans = 0;\n        for(int i = start; i <= limit; i++){\n            if(mask&(1<<i)) continue;\n            bool newprefix = isprefix ? (i == limit) : false;\n            ans += f(position+1,newprefix,mask | (1<<i),n,num);\n        }\n\n        return dp[position][isprefix][mask] = ans;\n    }\n\n    int permute(int n){\n        if(n == 1) return 9;\n        int fac = 362880;\n        int r = 9-n+1;\n\n        int num = 1;\n        for(int i=1; i <=r; i++){\n            num *= i;\n        }\n\n        return 9*fac/num;\n    }\n\n    int numDupDigitsAtMostN(int n) {\n\n        ios_base::sync_with_stdio(false);\n        cin.tie(NULL);\n        cout.tie(NULL);\n\n        string s = to_string(n);\n        int ans = 0;\n        // First Half\n        for(int i=1; i < s.length(); i++){\n            ans += permute(i);\n        }\n\n        //Second Half\n        memset(dp,-1,sizeof(dp));\n        ans += f(0,1,0,s.length(),s);\n        return n-ans;\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']