C++ ||  Digit DP Solution ||
Intuition\n Describe your first thoughts on how to solve this problem. \n\nlets build intuition from scratch. \nI will not direct jump into solution. \n(If you 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nlets build intuition from scratch. \nI will not direct jump into solution. \n**(If you don\'t have time to read whole article you can direct go to code).** \n\n\nSo , Let\'s start: \n\n```\nApproach - 1: \n```\n\nIterate from number 1 to n and then check that current number is valid or not ?\n\nThat is too basic right ?? and your n is 1e9 so that won\'t work here. \n\n```\nApproach - 2: \n```\n\nFrom above thing you have core concept like you have to build number and validate it without brutly gnerating whole number range. \n\n..... then what ?? \n\n**(Note : remember one thing . when you know what to do but stuck in complexity thing then just change the way you are iterating).** \n\n\nFirst of all , you are iterate whole number. \ncan you think any other way to build numbers ? \n\nwhat if we iterate on digits ?? \n\nlet say you know size of number string which is 5. \n\n_ , _ , _ , _ , _ . \n\nso for each index you can put digit from (0 to 9) and when you fill up all numbers then you validate is there any repeating digits or not, if yes then increase count. Right ?? \n\n*Yes , this is core logic. Now come to implementation part.* \n\n---\n\n\nThis kind of question you can solve easily with digit DP. \nI\'ll highly recommand to you to go through DIGIT DP thing and learn how to up "tight" , "index" and basic thing. \n\nNow , you can read further. \n\n`\nTask 1) `\n\nFor current index you decide your upper limit via tight varialble and all stuff (will not go into deep in this thing) , and now let say you have taken 3 for current index and have to check in previous index you have taken 3 or not, what is best way to do this ?\n\nYes , you can store bitmask of it and can check by set and unset bit either this digit have been taken or not.\n\nFrom here you know 3 states: \n```\n--> index. \n--> mask. \n--> tight. \n```\n\n\n`Task 2)` \n\nLet say n = 1000 , in digit DP you will take size of number string as length of maximum number and let say you want to generate lesser number then you can put 0 in front. \n\nWe have discussed that for each index we can choose digit from (0 to k) , where k is your upper bound based on tight variable. \n\nsee this case: 0010 , in this number we have taken 0 3 times , is that true ? \nNo. First 2 zeroes are just trailing zeroes and should not consider it into your mask. \n\nSo you have to keep one boolean variable , from left side when you take any noo-zero element then you mark it as 1 and now you have to take 0\'s in consideration. \n\n```\nYou got 4th state: \n--> taken. \n```\n`\nTask 3) `\n\nNow you have your number when you fill all the index, now how will you validate ? \n\nwill you store strings for number ?? No No that will be same as Approach - 1. \n\nNow when at current index from mask when you know that you have seen duplicate Digit , then mark one boolean variable as true to and pass it when you process for further index. \nSo that when you reach at out of bound index , means you have fill all digits. if that boolean variable 1 then you have to consider this otherwise not. \n\n```\nyou got 5th state: \n--> choose. \n```\n\n\n\n**You have 5 state which Generate 5-D DP.\nand then after i have taken standard template for digit DP.** \n\nNow you can go to code. \n\n```\nThanks to read upto here. \n\nDO UPVOTE TO MAKE ME HAPPY :))) \n```\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n[ 10*(1<<10)*(2)*(2)*(2) ] * 10 , here before 10 is our DP table and 10 is like 10 digits.  \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nour DP table, 10*(1<<10)*(2)*(2)*(2)\n\n# Code\n```\nclass Solution {\npublic:\n\n    long long dp[10][1<<10][2][2][2]; \n\n    long long solve(string & s , int index , int mask , int tight , int taken , int choose){\n        \n        if(index == s.size()) return choose; \n        if(dp[index][mask][tight][taken][choose] != -1) return dp[index][mask][tight][taken][choose]; \n\n        char k = \'9\'; \n        if(tight) k = s[index]; \n\n        long long ans = 0; \n        for(char c = \'0\' ; c <= k ; c++){\n            int ele = c-\'0\'; \n            if((1<<ele) & (mask)) \n            ans += solve(s , index+1 , ( (mask) | (1<<ele)) , tight && (c == k) , 1 , 1); \n            else {\n                if((c > \'0\') || (c == \'0\' && taken)){\n                    ans += solve(s , index+1 , ( (mask) | (1<<ele)) , tight && (c == k) , 1 , choose); \n                }\n                else ans += solve(s , index+1 , (mask) , tight && (c == k) , 0 , choose);\n            }\n        }\n        return dp[index][mask][tight][taken][choose] =  ans;\n    }\n    int numDupDigitsAtMostN(int n) {\n\n        memset(dp , -1 , sizeof(dp)); \n        string s = ""; \n        while(n){\n            s += (n%10 + \'0\'); \n            n /= 10;\n        }\n        reverse(s.begin() , s.end()); \n        return solve(s , 0 , 0 , 1 , 0 , 0) ; \n    }\n};\n```
['Math', 'String', 'Dynamic Programming', 'Backtracking', 'Bit Manipulation', 'Recursion', 'Memoization', 'Bitmask', 'C++']