1012. Numbers With Repeated Digits

Loading...LeetCode

挺有难度又挺好的一道题。计算 with repeated digits 的数字比较麻烦，直接做的话会 trapped in the puzzle of various cases. 不如直接计算 without repeated digits 的数字（which can be easily converted to a permutation problem），然后拿N减去，就得到答案了。

这样的话，对于一个 K 位的数，就只需要分两部分解决问题：

1. 位数 < K时有多少数字 without repeated digits（取值不设限）？

2. 位数 == K时有多少数字 without repeated digits （取值时需要让最后合成数 <= N）?

So the basic idea is, say we have a number 314159. We somehow turn it into [3,1,4,1,5,9]. Then we r going to do a lot of divide-and-conquers.

Divide-and-Conquer 1.

You probably already noticed if the the problem is "Count the Number Without Repeated Digit for in any number LESS THAN N=100 or 1000 or 10000 (any power of 10)". It is a relatively easier question. for N=100, the answer is 100- (9*8+9) . For N=1000, the answer is 1000 - (9*8*7 + 9*8 + 9)

Divide-and-Conquer 2.

Our real question has two aspects different from above. One, it is not asking less than LESS THAN '<', but is asking '<='. Two, N is something like 314159, not a power of 10. Since we can take care of numbers < 100000 as in Divide-and-Conquer 1, we only need to worry about 100000 - 314259.

Now we basically need to loop through [3,1,4,2,5,9] to find all the digit-unique 6-place numbers. Each time we are visiting ith place, the logic has 3 different variations.

2.a. If we are visiting 3 (first place), we need to visit 1,2. We are actually asking the question 'how many digit-unique 6-place numbers with leading 1 or 2?'. Well, why not 0? 0 has been calculated through 'Divide-and-Conquer 1'

2.b. If we are visiting 1-5 (2nd to 5th place), we need to visit any UNUSED values in 0 to (val-1). For example, if we are visiting 4 (3rd place), we are essentially answering this question: how many 31xxxx are digit-unique 6-place numbers? We need to try 310xxx 311xxx(No! 1 is USED) 312xxx 313xxx(No!3 is USED)

2.c. If we are visiting 9 (last place), we need to visit any UNUSED values in 0 to val. Why val not val-1? Because you need val to cover the exact case of 314259. (This iteration we are testing out 31425x).

为了解决 2.c 中的问题，我们在生成 digits 数组的时候，把最后一位加了1，这个padding操作可以 cover 掉最后一位数取值不设限的问题。

（事实上，直接把N+1也可以通过，但我自己没想通为什么，这样对于 999 这样的数字会改变K。）

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        def factorial(n):
            return n * factorial(n-1) if n > 1 else n
        # pick m out of n, ordred matters
        def permutation(m, n): return factorial(n) // factorial(n - m)
        
        # get the digits information
        digits = [int(d) for d in str(N)]
        # padding the last digit to cover its all cases
        digits[-1] += 1
        K = len(nums) # N has K digits
        cnt = 0 # number with no repeated val
        
        # count all **postive non-digit-repeating number with less than K digits
        for i in range(1, K): 
            cnt += 9 * P(i-1, 9)
            
        # count non-digit-repeating number number with K digits
        for i in range(K): 
            # prefix = nums[:i] + currentDigit
            # currentDigit < nums[i]
            for x in range(1 if i == 0 else 0, nums[i]):
                if x in digits[:i]: 
                    continue # avoid duplication
                cnt += P(K - (i + 1), 10 - (i + 1))
            
            # if current digit has already appeared in the former
            # any later case is invalid (has repeated digits)
            # so we don't need to keep going
            if digits[i] in digits[:i]: break
        
        return N - cnt