@@ -0,0 +1,1764 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Given a non-negative integer n, count all numbers with unique digits, x, where 0 %E2%89%A4 x %3C 10%5En.%0A * %3Cp%3E%0A * Example:%0A * Given n = 2, return 91. (The answer should be the total numbers in the range of 0 %E2%89%A4 x %3C 100, excluding%0A * %5B11,22,33,44,55,66,77,88,99%5D)%0A * %3Cp%3E%0A * Hint:%0A * %3Cp%3E%0A * A direct way is to use the backtracking approach.%0A * Backtracking should contains three states which are (the current number, number of steps to get that number and a%0A * bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and%0A * count all valid number till we reach number of steps equals to 10n.%0A * This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.%0A * Let f(k) = count of numbers with unique digits with length equals k.%0A * f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) %5BThe first factor is 9 because a number cannot start with 0%5D.%0A * %3Cp%3E%0A * Tags: Dynamic Programming, Backtracking, Math%0A */%0Apublic class CountingNumbersWithUniqueDigits %7B%0A%0A    /**%0A     * DP.%0A     * Think about how to use combination to build a number with unique digits.%0A     * f(1) = 10, f(2) = 9 * 9, f(3) = 9 * 9 * 8, f(4) = 9 * 9 * 8 * 7 ...%0A     * f(k) = 9 * 9 * 8 * ... * (9 - k + 2), 2 %3C= k %3C= 10%0A     * f(k) = f(10), k %3E 10%0A     */%0A    public int countNumbersWithUniqueDigits(int n) %7B%0A        if (n == 0) %7B%0A            return 1;%0A        %7D%0A        int res = 10;%0A        int uniqueDigits = 9;%0A        int availableNums = 9;%0A        while (n %3E 1 && availableNums %3E 0) %7B%0A            uniqueDigits *= availableNums;%0A            res += uniqueDigits;%0A            availableNums--;%0A            n--;%0A        %7D%0A        return res;%0A    %7D%0A%0A%7D%0A

add Counting Number with Unique Digits