Leetcode 1057 Solution

This article provides solution to leetcode question 1057 (numbers-with-repeated-digits)
Categories:
Tags:
Access this page by simply typing in "lcs 1057" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/numbers-with-repeated-digits

Solution

#!/usr/bin/env python3


class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        digits = list(map(int, str(N + 1)))
        n = len(digits)

        def A(m, n):
            return A(m - 1, n - 1) * m if n else 1

        ans = 0
        for i in range(1, n):
            ans += 9 * A(9, i - 1)

        s = set()
        for i, digit in enumerate(digits):
            for j in range(0 if i else 1, digit):
                if j in s:
                    continue
                ans += A(9 - i, n - i - 1)
            if digit in s:
                break
            s.add(digit)

        return N - ans