Friday, June 24, 2016

LeetCode OJ - Count Numbers with Unique Digits

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