902. Combination of digits up to N: classic “digit DP + dichotomy” problem

Make writing a habit together! This is the 13th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

Topic describes

This is 902 on LeetCode, a combination of numbers up to N and difficulty is difficult.

Tag: “Dynamic programming”, “binary”, “Digital DP”

Given an array of digits in non-decreasing order. You can write any number digits[I]digits[I]digits[I]digits[I]. For example, if digits=[1,3,5]digits =[1,3,5]digits =[1,3,5]digits =[1,3,5], we can write numbers like ’13’, ‘551’, and ‘1351315’.

Returns the number of positive integers that can be generated less than or equal to the given integer NNN.

Example 1:

Input: digits = ["1","3","5","7"], n = 100 output: 20 Explanation: The 20 numbers to write are: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.Copy the code

Example 2:

Digits = ["1","4","9"], n = 1000000000 We can write three one-digit digits, nine two-digit digits, 27 three-digit digits, 81 four-digit digits, 243 five-digit digits, 729 six-digit digits, 2187 seven-digit digits, 6561 eight-digit digits, and 19,683 nine-digit digits. In total, 29,523 integers can be written using the numbers in D.Copy the code

Example 3:

Input: digits = ["7"], n = 8 Output: 1Copy the code

Tip:

• 
  $1 <= digits.length <= 9$
• 
  $digits[i].length == 1$
• 
  $digits[i]$from'1' 到 '9'The number of
• digitsAll values in
• digitsIn non-decreasing order
• 
  $1 <= n <= 10^9$

Digit DP plus two PI

This is a “digital DP” classic use of the problem.

Since the digits given in the question does not contain 000, it is equivalent to answering only how many digits in the range [1,x][1, x] can be covered by the number using digits.

Start by converting the string array digits to nums, assuming nums has length MMM, and then consider how to find the number of valid digits in the range [1,x][1, x].

If we have a function int dp(int x), which can return the number of valid numbers in the interval [1,x][1, x][1,x], then we can answer the query of any valid number in the interval with the “exclusion principle” :

In this case, the left endpoint of the query interval is 111, and dp(0)=0dp(0) =0dp(0) =0.

Then consider how to implement the function int dp(int x), we divide the legal numbers that comprise [1,x][1, x][1,x] into three categories:

• Figures and
  $x$Same, and highest bit ratio
  $x$The highest digit is going to be small, and this part is going to be zerores1;
• Figures and
  $x$Same, and the highest bit and
  $x$If the highest bit is the same, this part of the statistics isres2;
• Digits than
  $x$Little, this part of the statistics is zerores3.

Among them, the solution of RES1 and RES3 is relatively simple, and the focus is on how to solve res2.

right
$x$Perform “high to low” processing (assume
$x$Digital for
$n$), for no
$k$In terms of (
$k$Not the highest bit), assuming at
$x$In the first
$k$Bit is
$cur$, so in order to satisfy the “size constraint” relationship, we can only
$[1, cur – 1]$The range takes the number while satisfying “the number can only be taken fromnums“So we can make use ofnumsIt’s ordered, it’s dichotomized, it’s satisfiednums[mid] <= curMaximum subscript of
$r$, according to the
$nums[r]$ 与
$cur$Are discussed in different cases:

• nums[r]=curnums[r] = curnums[r]=cur: Since nums[I]nums[I]nums[I] can be used multiple times, each position has a variety of MMM options, a total of N − Pn-PN − P positions, Therefore, there are r∗ Mn − PR * m^{n-p}r∗ Mn − P legal schemes in this branch. Since nums[r]=curnums[r] =curnums[r] =cur, there are branches to be decided in the future (need statistics), so we need to continue processing;
• 
  $nums[r] < cur$: Count now
  $nums[r]$Position,
  $k$A total of
  $r + 1$A variety of options are available for each position behind
  $nums[i]$It can be used multiple times, in every location
  $m$Kind of choice, common
  $n – p$So this branch is shared
  $(r + 1) * m^{n – p}$Kind of a legal solution because
  $nums[r] < cur$, the number of subsequent schemes (all satisfying the relation of less than) has been counted this time, and is carried out after accumulationbreak;
• 
  $nums[r] > cur$: This branch no longer meets the requirements of “size limit”, and the number of legal schemes is
  $0$Directly,break.

Other details: In fact, we can combine the res1 and RES2 cases.

Code:

class Solution {
    int[] nums;
    int dp(int x) {
        List<Integer> list = new ArrayList<>();
        while(x ! =0) {
            list.add(x % 10);
            x /= 10;
        }
        int n = list.size(), m = nums.length, ans = 0;
        // The number of digits is the same as x
        for (int i = n - 1, p = 1; i >= 0; i--, p++) {
            int cur = list.get(i);
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= cur) l = mid;
                else r = mid - 1;
            }
            if (nums[r] > cur) {
                break;
            } else if (nums[r] == cur) {
                ans += r * (int) Math.pow(m, (n - p));
                if (i == 0) ans++;
            } else if (nums[r] < cur) {
                ans += (r + 1) * (int) Math.pow(m, (n - p));
                break; }}// The number of bits less than x
        for (int i = 1, last = 1; i < n; i++) {
            int cur = last * m;
            ans += cur; last = cur;
        }
        return ans;
    }
    public int atMostNGivenDigitSet(String[] digits, int max) {
        int n = digits.length;
        nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(digits[i]);
        returndp(max); }}Copy the code

• Time complexity: due todigitsThere is at most
  $9$, so the binary complexity can be ignored, and the overall complexity is
  $O(\log{n})$
• Space complexity: O(C)O(C)O(C)

The last

This is the No.902 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.