Leetcode: Count Numbers with Unique Digits

Count Numbers with Unique Digits



Similar Problems:


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

Example:

Given n = 2, return 91. (The answer should be the total numbers in the range of 0 <= x < 100, excluding [11,22,33,44,55,66,77,88,99])

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/count-numbers-with-unique-digits
// Basic Ideas: dynamic programming
//   dp(i): How many unique digits with length of i
//
// Complexity: Time O(n*n), Space O(1)
func countNumbersWithUniqueDigits(n int) int {
    if n == 0 { return 1 }
    if n == 1 { return 10 }
    res := 10
    for i:=2; i<=n; i++ {
        count := 9
        for j := i-1; j>=1; j-- {
            count = count * (10-j)
        }
        res += count
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.