Python 5 lines with explanation

  • 0

    This is a classic combinatorics problem. In order to count all distinct numbers, we go digit by digit.

    We can choose digits using the following rules:
    1st digit: 1-9
    2nd - nth digit: 0-9

    In order to ensure distinctness of digits, we need to add more rules on 2nd to nth digits.
    2nd digit can now only select from 0-9 except the first digit, 9 - 1 = 8 choices
    3rd digit can now select from 0-9 except the first two digits, 9 - 2 = 7 choices
    nth digit follows the same rules. 9 - (n-1) choices, if n == 10, then we have 0 choices left.

    Putting the above rules into some compact code, we get the following:

    def countNumbersWithUniqueDigits(self, n):
        from operator import mul; from functools import reduce
        s = 1
        for i in range(1,n+1):
            s += 9 * reduce(mul, [j for j in range(9, 9-i+1,-1)], 1)
        return s

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.