constant time combinatorial counting
(A similar problem: https://leetcode.com/problems/ones-and-zeroes/)\n\nIf you studied probability, it is well known that considering the complement problem: \'t
(A similar problem: https://leetcode.com/problems/ones-and-zeroes/)\n\nIf you studied probability, it is well known that considering the complement problem: \'the count of number WITHOUT repeating digit that\'s less than N\' is easier to solve. And then we get the answer by subtracting this cnt from N.\n\nSo numbers M without repeating digits that\'s less than N has three types:\n1. M has the same prefix as N.\n2. M has the same length but the leading digit is non-zero and strictly less than leaading digit as N.\n3. M has strictly less digits than N.\n\nWe can count type (1)-(2) together, and (3) later.\ntype 1 and 2 requires us to remember the number of digit that\'s not used in the prefix but strictly less than the current digit. Let\'s see an example.\nSuppose N = 453232\n\ntype (1) are of the form 3xxxxx, 2xxxxx, 1xxxxx, the leading digit has 4-1 = 3 choices. Then the xxx part we can use whatever number, but not the choice of our leading digit, so that\'s 9\\*8\\*7\\*6\\*5, which we call perm(9,5).\ntype (2) are of the form 4yxxxx, 45yxxx, 453yxx, 4532yx, but we can\'t consider 45323x(?) because we see a repeating digit. so starting from the MSD we\'ll just count up to the first time we see a repeating digit in N.  Notices that I put \'y\' instead of \'x\' for the first digit after the prefix. For 4yxxxx, since N = 453232, we can\'t use y to be greater than 5. so we use 3, 2, or 1, or 0. Notice that we can\'t use 4, because 4 has appeaered in the prefix. Anyhow, we use an array to store the number of digits available at i-th index that\'s strictly less than the ith-indes of N and hasn\'t been used in the prefix so far.\n\nFor type (3), we always have 9 choice for MSD, 9 choice for 2nd digit, 8 choice for 3rd digit. Using N=543232 as same exmaple, type (3) would cover 1000-9999, 100-999, 10-99, 0-9. Simple counting problem.\n\nNow subtract type (1) +(2)+(3) from N, that\'s the answer we have. \n\n```\nclass Solution {\n    public int numDupDigitsAtMostN(int N) {\n        int ans = 0;\n\n        String num = Integer.toString(N);\n        //Convert N to an array of digits for easy proccessing. A[0] stores the most sigifinicant digit.\n        int[] A = new int[num.length()];\n        for(int i = 0;i<A.length; i++){\n            A[i] = num.charAt(i)-\'0\';\n        }\n        //cnt array stores the number of digit strictly smaller than A[i] and hasn\'t been used in the prefix. \n        int[] cnt = new int[A.length];\n        boolean[] used = new boolean[10];\n        used[A[0]] = true;\n        //we require the most significant digit to be non-zero.\n        cnt[0] = A[0]-1;\n        //rpt: The first repeating idx, after this idx, no number with the same prefix as N and is smaller than N has no repeating digit. So stop counting.\n        int rpt = A.length;\n        \n        for(int i=1;i<A.length; i++){\n            for(int j = 0;j<A[i];j++){\n                if(!used[j]) cnt[i]++;\n            }\n            if(used[A[i]]){\n                rpt=i;\n                break;\n            }\n            used[A[i]] = true;\n        }\n        \n        //count from most significant digit, the number of no repeating number with same prefix and has same length with N. \n        \n        for(int i = 0;i<rpt; i++){\n            int c = cnt[i];\n            c*=perm(9-i,A.length-i-1);\n            ans+=c;\n        }\n        //if there\'s repeating idx, count that in.\n        if(rpt!=A.length) ans+= cnt[rpt]*perm(9-rpt, A.length-rpt-1);\n        \n        //Now count the numbers which has length strictly less than N.\n        for(int i = 1;i<A.length;i++){\n            ans+= 9*perm(9,A.length-i-1);\n        }\n        if(rpt==A.length) ans++;\n        return N-ans;\n    }\n    \n    public int perm(int n, int k){\n        int a= 1;\n        for(int i = 0;i<k;i++){\n            a*=(n-i);\n        }\n        return a;\n    }\n    \n}\n```
[]