**Problem:**

Please find the problem here.

**Analysis:**

It is easy to see there if we have more than 10 digits, then it is impossible for us to not have a repeated digit. So the program can only accept 1 - 10 as input, for any other input we just return 0.

We can think of the the numbers be arranged in a tree like this:

The root is an empty string that we don't care. Each node has a unique path back to the root, and that path (from top to bottom) represents a number. By carefully crafting the tree, we can be sure that all numbers with unique digits are covered, so the remaining is just counting the number of nodes.

Note that the number 0 is not there, and we can associate that with the root node.

**Solution:**

The number of nodes in the root layer is 1

The number of nodes in the second layer is 9

The number of nodes in the third layer is 9 x 8

... and so on ...

So it is easy to see the answer is $ 1 + 9 + 9 \times 8 + \cdots $

To make the submission super quick, we can pre-compute the answers (after all, there are only 10 answers, so we can compactly switch it)

**Code:**

#include "stdafx.h" // https://leetcode.com/problems/count-numbers-with-unique-digits/ #include "LEET_COUNT_NUMBERS_WITH_UNIQUE_DIGITS.h" #include <map> #include <iostream> #include <sstream> #include <set> #include <string> using namespace std; namespace _LEET_COUNT_NUMBERS_WITH_UNIQUE_DIGITS { class Solution { public: int countNumbersWithUniqueDigits(int n) { switch (n) { case 0: return 1; case 1: return 10; case 2: return 91; case 3: return 739; case 4: return 5275; case 5: return 32491; case 6: return 168571; case 7: return 712891; case 8: return 2345851; case 9: return 5611771; case 10: return 8877691; default: return 0; } } }; }; using namespace _LEET_COUNT_NUMBERS_WITH_UNIQUE_DIGITS; int LEET_COUNT_NUMBERS_WITH_UNIQUE_DIGITS() { Solution s; cout << s.countNumbersWithUniqueDigits(3) << endl; return 0; }

## No comments :

## Post a Comment