#902

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Numbers At Most N Given Digit Set

The 'Numbers At Most N Given Digit Set' problem requires calculating how many numbers can be formed using a given digit set and are less than or equal to a target number.

array math string binary search dynamic programming

Problem Statement

Given an array of digits sorted in non-decreasing order, you can form numbers by selecting digits from the array repeatedly. For example, if digits = ['1', '3', '5'], you can form numbers like '13', '551', and '1351315'.

The goal is to return the total number of positive integers that can be created using the digits and are less than or equal to a given integer n.

Examples

Example 1

Input: digits = ["1","3","5","7"], n = 100

Output: 20

The 20 numbers that can be written are: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Example 2

Input: digits = ["1","4","9"], n = 1000000000

Output: 29523

We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers, 81 four digit numbers, 243 five digit numbers, 729 six digit numbers, 2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers. In total, this is 29523 integers that can be written using the digits array.

Example 3

Input: digits = ["7"], n = 8

Output: 1

Example details omitted.

Constraints

1 <= digits.length <= 9
digits[i].length == 1
digits[i] is a digit from '1' to '9'.
All the values in digits are unique.
digits is sorted in non-decreasing order.
1 <= n <= 109

Solution Approach

State Transition Dynamic Programming

The solution involves a dynamic programming approach where we track the number of valid numbers based on their length and whether they are still less than or equal to n. At each step, we transition between states where we either maintain the constraint or generate new possibilities.

Digit-wise Calculation

Start by counting all valid numbers that can be formed with fewer digits than n. Then, proceed digit by digit, ensuring each newly formed number is valid under the constraint of being less than or equal to n.

Optimization with Binary Search

Using binary search on the sorted digit array allows for quick determination of the largest valid digit that can be placed at each position without violating the n constraint. This helps reduce unnecessary calculations during state transitions.

Complexity Analysis

Metric	Value
Time	O(\log N)
Space	O(\log N)

The time complexity of the solution is O(log N), where N is the target number. This is because we use binary search and state transition based on the number of digits in n. The space complexity is O(log N), as we only need to store intermediate results for each digit length up to the number of digits in n.

What Interviewers Usually Probe

Look for the candidate's ability to break down the problem into sub-problems based on the number of digits and constraints.
Assess how well the candidate can implement dynamic programming and apply the state transition efficiently.
Gauge the candidate’s understanding of optimization techniques like binary search within dynamic programming solutions.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the digit-wise approach, resulting in an inefficient solution that doesn't properly account for each digit's contribution to the overall count.
Not correctly handling the constraint of being less than or equal to n when transitioning between states, leading to over-counting of invalid numbers.
Failure to optimize the solution using binary search, leading to unnecessary brute-force calculations.

Follow-up variants

Consider cases where digits have only one element, which limits the number of possible numbers.
Handle very large n values efficiently, ensuring the solution scales to n values close to 10^9.
Test the algorithm with various sets of digits, including edge cases like the smallest possible n.

FAQ

What is the main pattern used in the 'Numbers At Most N Given Digit Set' problem?

The problem uses state transition dynamic programming to count valid numbers formed from a given digit set that are less than or equal to a target number.

How does binary search help in solving the 'Numbers At Most N Given Digit Set' problem?

Binary search helps optimize the solution by efficiently determining the largest valid digit that can be used at each position while maintaining the constraint of being less than or equal to n.

What is the time complexity of solving 'Numbers At Most N Given Digit Set'?

The time complexity is O(log N), where N is the target number. This is because we perform binary search and track the number of digits in n.

What happens if the digit set contains only one element?

If the digit set contains only one element, the problem reduces to counting how many times that digit can form valid numbers less than or equal to n.

How can I avoid over-counting invalid numbers in this problem?

Ensure that during state transitions, you check whether the current number formed still respects the constraint of being less than or equal to n.

terminal

Solution

Solution 1: Digit DP

This problem essentially asks for the number of positive integers that can be generated from the digits in digits within the given range $[l, .., r]$. The count depends on the number of digits and the value of each digit. We can solve this problem using the Digit DP approach. In Digit DP, the size of the number has little impact on the complexity.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        @cache
        def dfs(i: int, lead: int, limit: bool) -> int:
            if i >= len(s):
                return lead ^ 1

            up = int(s[i]) if limit else 9
            ans = 0
            for j in range(up + 1):
                if j == 0 and lead:
                    ans += dfs(i + 1, 1, limit and j == up)
                elif j in nums:
                    ans += dfs(i + 1, 0, limit and j == up)
            return ans

        s = str(n)
        nums = {int(x) for x in digits}
        return dfs(0, 1, True)

Continue Practicing

#792 number of matching subsequences #943 find the shortest superstring #996 number of squareful arrays