902.md

902 Numbers At Most N Given Digit Set

Description

link

---

Solution

explanation:

• N has n digits, so all numbers less than n digits are valid, which are: sum(len(D) ** i for i in range(1, n))
• The loop is to deal with all numbers with n digits, considering from N[0], N[1] back to N[n-1]. For example, N[0] is valid only for c in D if c <= N[0]. If c < N[0], then N[1], ..., N[n-1] can take any number in D but if c == N[0], then we need consider N[1], and the iteration repeats. That's why if N[i] not in D, then we don't need to repeat the loop anymore.
• Finally i==n is addressed at the end when there exists all c in D that matches N

---

Code

Complexity T : O(log(N)) M : O(n)

class Solution:
    def atMostNGivenDigitSet(self, D, N):
        """
        :type D: List[str]
        :type N: int
        :rtype: int
        """
        N = str(N)
        n = len(N)
        
        res = sum(len(D) ** i for i in range(1, n))
        
        i = 0
        while i < n:
            res += sum(c < N[i] for c in D) * (len(D) ** (n - i - 1))
            if N[i] not in D:
                break
            i += 1
            
        return res + (i == n)