very simple digit DP even beginners can understand
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem seems to involve counting the number of unique digits in numbers up to a gi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem seems to involve counting the number of unique digits in numbers up to a given value n. The use of dynamic programming suggests that there might be overlapping subproblems that can be optimized.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAnswer can be **total numbers - numbers with only unique digits**\n\nFirst understand the bitmask , dont worry it is easy ,lemme tell you how\n \nMaximum number of digits are (0-9) is 10. So, think like in bits we use 0th bit for 0 digits and so on . So, for 10 total digits we can use :-\n9 8 7 6 5 4 3 2 1 0\n**1 1 1 1 1 1 1 1 1 1** -->(1023 in bits)\nif we use any digit we can set the digit bit to off. What I mean to say is if we use 5 digit in the answer then the bit representation of mask will 1 1 1 1 0 1 1 1 1 1 which represent we use 5 th digit so infuture for ongoing recursion call we cant have 5 in the digit. You can look at the code if you know xor properties to turn off bit at a specific position or you can google that it is very simple.  \n\nThere is one more concept of leading zeroes and we have to keep the track of it why? because 00003 is a number and 3 is also a number\nbut in 00003 zero is repeated and in 3 no zero is repeated,  this means  till 0000 number is not stared and from 3 number is started if number is not started then we dont need to add that in ans i used z for leading zeroes 1 for yes and 0 for no.\n\nTightness implies that a digit at a particular position cannot exceed a certain limit to maintain the given condition.\nif my max number is 545454\nthen first digit i can\'t use more than 5, if use anything less then there will be no tightness. This will tell if the current digits range is restricted or not. If the current digit\u2019s \nrange is not restricted then it will span from 0 to 9 (inclusively) else it will span \nfrom 0 to digit[idx] (inclusively).\nExample: consider our limiting integer to be 3245 and we need to calculate G(3245) \nindex : 4 3 2 1 \ndigits : 3 2 4 5 \n \nUnrestricted range: \nNow suppose the integer generated till now is : 3 1 * * ( * is empty place, where digits are to be inserted to form the integer). \n\n  index  : 4 3 2 1  \n  digits : 3 2 4 5\n generated integer: 3 1 _ _ \nhere, we see that index 2 has unrestricted range. Now index 2 can have digits from range 0 to 9(inclusively). \nFor unrestricted range tight = 0\nRestricted range: \nNow suppose the integer generated till now is : 3 2 * * ( \u2018*\u2019 is an empty place, where digits are to be inserted to form the integer). \n\n  index  : 4 3 2 1  \n  digits : 3 2 4 5\n generated integer: 3 2 _ _ \nhere, we see that index 2 has a restricted range. Now index 2 can only have digits from range 0 to 4 (inclusively) \nFor restricted range tight = 1\n\nNow you can understand the problem and able to understand the code you do it without dp as the constraint are small Trust me with only recursion TC-> logn.\n\nThe code utilizes a dynamic programming approach to **count the number of unique digits**. The function dfs recursively explores different digit combinations while considering constraints like tightness and a bitmask to track used digits. The dynamic programming array dp is used to memoize results and avoid redundant calculations.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nnear about **O(1)** because of constant time\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nnear about **O(1)** because of constant space\n\n# Code\n```\nclass Solution {\n    int dp[12][2][1024];\n    int dfs(string &s, int i, int z, int tight , int mask){\n        if(i==s.length()){\n            if(!z)return 1;\n            return 0;\n        }\n        if(dp[i][tight][mask]!=-1)return dp[i][tight][mask];\n        int limit = tight == 1? s[i]-\'0\':9;\n        int ans = 0;\n        for(int j=0;j<=limit;j++){\n            int t = tight&(j==limit);\n            int nz = z & (j==0);\n            if(nz){\n                ans+= dfs(s,i+1,nz,t,mask);\n            }\n            else{\n                if(mask>>j & 1){\n                    int nm = mask ^ (1<<j);\n                    ans += dfs(s,i+1,nz,t,nm);\n                }\n            }\n        }\n        return dp[i][tight][mask] = ans;\n    }\npublic:\n    int numDupDigitsAtMostN(int n) {\n        string s = to_string(n);\n        memset(dp,-1,sizeof(dp));\n        return n - dfs(s,0,1,1,1023);\n    }\n};\n```\n\n**SORRY FOR MY ENGLISH **\n\n\n
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']