online advertising

Friday, June 24, 2016

LeetCode OJ - Count Numbers with Unique Digits


Please find the problem here.


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.


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)


#include "stdafx.h"


#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <string>

using namespace std;

    class Solution
        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;


    Solution s;
    cout << s.countNumbersWithUniqueDigits(3) << endl;
    return 0;

No comments :

Post a Comment