Count Numbers with Unique Digits

Problem: Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

Example:

Input: 2
Output: 91 
Explanation: The answer is the total numbers in the range of 0 ≤ x < 100, excluding numbers with non-unique digits like 11,22,33,44,55,66,77,88,99 so output is 100 - 9 = 91

Approach: If you think about it, it's a very simple problem to solve. Let's take an example of n = 3 that means we need to find all numbers with unique digits in the range [0,  1000). That means all the 1 digit numbers, 2 digit numbers and 3 digit numbers with unique digits.

Now let's see how to calculate numbers with unique digits:

To get the all the 3 digit numbers with unique digits, lets start with the most significant position to least significant position:

• At position 1, we have total 9 options as 0 can't be at most significant position. (1 - 9)
• At position 2, we again have total 9 options as now 0 can be included but we can't include the digit which is used at position 1. (0 - 9) minus the digit at position 1.
• At position 3, we have total 8 options as we can't include the digits which are used at position 1 and position 2.

So now if you see the total number of 3 digit numbers with unique digits are 9 * 9 * 8 = 648.

To get all the 2 digit numbers with unique digits, we will follow the same steps:

• At position 1, we have total 9 options as 0 can't be at most significant position. (1 - 9)
• At position 2, we again have total 9 options as now 0 can be included but we can't include the digit which is used at position 1. (0 - 9) minus the digit at position 1.

So total number of 2 digit numbers with unique digits are 9 * 9 = 81.

Total number of 1 digit number with unique digits = 10 (0 - 9).

So total count of numbers with unique digits in range [0 - 10^3) = [0 - 999] is 648 + 81 + 10 = 739. 

Algorithm should be clear now. In the same way we can calculate it for any n. 

 

Implementation in C#:

        public static int CountNumbersWithUniqueDigits(int n)

        {

            if (n == 0)

            {

                return 1;

            }

            if (n == 1)

            {

                return 10;

            }

            int prev = 10;

            int result = 0;

            for (int i = 2; i <= n; ++i)

            {

                // For first digit we always have 9 options as 0 can't be at most significant / highest position

                int totalOptions = 9;

                // For next significant position we have 9 options as it can include 0

                int currentNumberOfOptions = 9;

                for (int j = 1; j < i; ++j)

                {

                    totalOptions *= currentNumberOfOptions;

                    --currentNumberOfOptions;

                }

                result = prev + totalOptions;

                prev = result;

            }

            return result;

        }

Complexity: O(n^2)