Java O(1) 0ms beats all
This is to count the numbers with all distinct digits.\nWe can separate into two parts... say for N = 6,543,210,\n\nwe\'ll count the distinct one from 1 to 999,
This is to count the numbers with all distinct digits.\nWe can separate into two parts... say for N = 6,543,210,\n\nwe\'ll count the distinct one from 1 to 999,999, which would be \n\t1-9: 9\n\tplus 10-99: 9 * 9 \n\tplus 100-999: 9 * 9 * 8\n\tplus 1,000 - 9,999: 9 * 9 * 8 * 7\n\t...\n\t100,000 - 999,999: 9 * 9 * 8 * 7 * 6 * 5.\n\t\nThe above part can be done in one for loop with at most 9 iterations : O (1)\t\n\nThen we add the remaining distinct ones (from 1,000,000 to 6,543,210)\n\nFrom 1,000,000 to 5,999,999 : 5 * 9 * 8 * 7 * 6 * 5 * 4\nthen 6,000,000 to 6,499,999: 5 * 9 * 8 * 7 * 6 * 5\nthen 6,500,000 to 6,539,999 and so on... 4 * 9 * 8 * 7 * 6 ...\n\nThe above part takes at most 81 iterations which is also O(1)\n\n```\nclass Solution {\n    public int numDupDigitsAtMostN(int N) {\n        if (N<=10)\n            return 0;\n        int[] digits = new int[9];\n        int cursor = 0;\n        int v = N;\n        while (v>0){\n            digits[cursor++] = v%10;\n            v= v/10;\n        }\n        //cursor is digit cnt\n        return N - countDistinctUpToMsb1(cursor) - countDistinctFromMsb1(digits, cursor);\n    }\n    \n    private int countDistinctUpToMsb1(int digitCnts){\n        int total = 9;\n        int last = 9;\n        int remainingCnt = 9;\n        for (int i=1;i<digitCnts-1;i++){\n            last = last * remainingCnt;\n            total += last;\n            remainingCnt--;\n        }\n        return total;\n    }\n    \n    private int countDistinctFromMsb1(int[] digits, int length){\n        //eg 1000 - 2345\n        boolean[] digitUsed = new boolean[10];\n        int count = 0;\n        for (int i=0;i<length;i++){\n            int digit = digits[length-i-1];\n            count += countDistinct(digitUsed, i, digit, i==0?false:true,length-i-1);\n            if (digitUsed[digit])\n                break;\n            if (i==length-1)\n                count++;\n            digitUsed[digit] = true;\n        }\n        return count;\n    }\n    private int countDistinct(boolean[] digitUsed,int digitUsedCnt, int nextDigit, boolean nextFromZero, int tailingZeros){\n        int cnt=0;\n        for (int i=nextFromZero?0:1;i<nextDigit;i++){\n            if (!digitUsed[i])\n                cnt++;\n        }\n        digitUsedCnt++;\n        for (int i=0;i<tailingZeros;i++){\n            cnt *= (10 - digitUsedCnt++);\n        }\n        return cnt;\n    }\n}\n```
[]