## Friday, June 24, 2016

### LeetCode OJ - Count Numbers with Unique Digits

Problem:

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;
}