LeetCode 902 - Numbers At Most N Given Digit Set


https://leetcode.com/problems/numbers-at-most-n-given-digit-set/
We have a sorted set of digits D, a non-empty subset of {'1','2','3','4','5','6','7','8','9'}.  (Note that '0' is not included.)
Now, we write numbers using these digits, using each digit as many times as we want.  For example, if D = {'1','3','5'}, we may write numbers such as '13', '551', '1351315'.
Return the number of positive integers that can be written (using the digits of D) that are less than or equal to N.

Example 1:
Input: D = ["1","3","5","7"], N = 100
Output: 20
Explanation: 
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: D = ["1","4","9"], N = 1000000000
Output: 29523
Explanation: 
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 of D.
Approach 1: Dynamic Programming + Counting
Time complexity: O(log10(N))
Space complexity: O(1)
Suppose N has n digits.

less than n digits

We can use all the numbers from D to construct numbers of with length 1,2,…,n-1 which are guaranteed to be less than N.
e.g. n = 52125, D = [1, 2, 5]
format X: e.g. 1, 2, 5 counts = |D| ^ 1
format XX: e.g. 11,12,15,21,22,25,51,52,55, counts = |D|^2
format XXX:  counts = |D|^3
format XXXX: counts = |D|^4

exact n digits

if all numbers in D  != N[0], counts = |d < N[0] | d in D| * |D|^(n-1), and we are done.
e.g. N = 34567, D = [1,2,8]
we can make:
  • X |3|^1
  • XX |3| ^ 2
  • XXX |3| ^ 3
  • XXXX |3| ^ 3
  • 1XXXX, |3|^4
  • 2XXXX, |3|^4
  • we can’t do 8XXXX
Total = (3^1 + 3^2 + 3^3 + 3^4) + 2 * |3|^ 4 = 120 + 162 = 282
N = 52525, D = [1,2,5]
However, if d = N[i], we need to check the next digit…
  • X |3|^1
  • XX |3| ^ 2
  • XXX |3| ^ 3
  • XXXX |3| ^ 3
  • 1XXXX, |3|^4
  • 2XXXX, |3|^4
  •  5????
    • 51XXX |3|^3
    • 52???
      • 521XX |3|^2
      • 522XX |3|^2
      • 525??
        • 5251X |3|^1
        • 5252?
          • 52521 |3|^0
          • 52522 |3|^0
          • 52525 +1
total = (120) + 2 * |3|^4 + |3|^3 + 2*|3|^2 + |3|^1 + 2 * |3|^0 + 1 = 120 + 213 = 333
if every digit of N is from D, then we also have a valid solution, thus need to + 1
  public int atMostNGivenDigitSet(String[] D, int N) {
    char[] s = String.valueOf(N).toCharArray();
    int n = s.length;
    int ans = 0;
    for (int i = 1; i < n; ++i)
      ans += (int)Math.pow(D.length, i);
    for (int i = 0; i < n; ++i) {
      boolean prefix = false;
      for (String d : D) {
        if (d.charAt(0) < s[i]) {
          ans += Math.pow(D.length, n - i - 1);
        } else if (d.charAt(0) == s[i]) {
          prefix = true;
          break;
        }
      }
      if (!prefix) return ans;
    }
    return ans + 1;
  }
(数位统计) O(logN)O(log⁡N)
假设数字 N 有 L 位，D 总共有 n 个数字，那么低于 L 位数的所有数字都可以随意拼成，这一部分总共有 ∑L−1i=1ni∑i=1L−1ni 个整数可以拼成。
接下来从数字 N 的最高位开始分析（第 L 位到第 1 位），如果 D 中没有数字小于等于当前位 s[i]，则可以直接返回答案；
若 D 中有数字等于当前位 s[i]，且有 j 个数字小于当前位 s[i]，则当前答案统计 j⋅ni−1j⋅ni−1；
若 D 中没有数字等于当前为 s[i]，且有 j 个数字小于当前位 s[i]，则当前答案统计 j⋅ni−1j⋅ni−1，然后返回答案。
最后若退出了循环而没有返回，返回答案加一，这是因为最后等于 N 的数字需要被统计。
时间复杂度
每个数位被遍历常数次，故时间复杂度为 O(logN)O(log⁡N)。
Tips
这类数位统计题的一般技巧是从高位开始，累加小于当前数字的所有情况，然后令当前位和限制的数字相同，继续往低位累加。
（1）首先明确一个问题，就是给的数字集合 D 是不重复的，感觉这一点还是很重要的。 
（2）假设数字 N 为 K 位， 很显然，K-1 的数字一定比它小，那么能组成 K-1 位的数有多少那？答案为(K-1)^(len(D))，理解就是每一位有 len(D) 种选择，所以是它的次方个。 
（3）由（2）可以求出位数为1 - (K-1) 位 的数的个数了，现在位数为 K，其比 N 小的数字怎么求？动态规划方法。 
（4）–求位数为K且小于 N 的数字个数–， 思路： 
（5）从数据集D中依次拿出 一个数去和N的最高位比较，如果比它小，后面各个位上的数字可以任意组合，通过求次方就可以得到。 
（6）如果比它小，很显然，后面再怎么组合也是不符合要求的，所以直接舍弃。 
（7）如果相等，现在也很显然，竟然最高位相等，那么就可以直接等于次高位符合要求的个数（形成子问题 – 动态规划的一个必要条件）。然后把所有的累加，就是位数为 K 且小于N的数字个数。

 dp状态方程如下：

 设：dp[i:] 表示，从左向开始，第 i 个数字表示最高位时的，符合要求的数字个数。

 for i in range(K-1, -1, -1):
    for d in D:
        if d < S[i]:
            dp[i] += len(D) ** (K-i-1)
        elif d == S[i]:
            dp[i] += dp[i+1]
我想，第一个问题是，这到底是一个统计问题，还是一个计算问题。考虑到N的范围，显然不能直接遍历所有数进行统计，而是需要进行某种程度的计算。也许会涉及到组合数。（虽然事实是没有）
第二个问题是正着做还是反着做——计算只包含这些数字的数的个数，还是计算不只包含这些数字的数的个数？显然我比赛的时候完全没有想清楚这一点，但就这道题来说，大概计算包含更简单一点。

包含X数字的数”也许不算是一种常见的题型，但用非统计的方法计算在某个范围内符合某条件的数的数量似乎还挺常见的（如Leetcode 866）。但我觉得这些题目之间的共性并不大。
如何寻找<=N的合法的数？显然可以根据数的长度进行分类讨论。[1]对于长度小于len(N)的那些，显然D中数字的任意组合均是合法的（这一点我之前居然没有意识到……）；对于长度和len(N)相等的那些，则需要分类讨论：
  • 如果该数首位比N的首位小，则之后的数字可以任意组合；如果该数首位和N的首位相等（当然前提是N的首位也是一个合法数字），则需要继续讨论第2位
  • 如果该数第2位比N的第2位小，则之后的数字可以任意组合；如果该数第2位和N的第2位相等（当然前提是N的第2位也是一个合法数字），则需要继续讨论第3位
  • 以此类推……
于是我们就得到了一个递推算法：令f[i]表示<= N[i:]的数的数量（i从1开始编号），则

1
f[i] = (number of digits < N[i]) * (D.size)^(len - i) + (N[i] in D) * f[i + 1]
且最终的结果为

1
f[1] + (D.size)^(len - 1) + (D.size)^(len - 2) + ... + D.size


First, call a positive integer X valid if X <= N and X only consists of digits from D. Our goal is to find the number of valid integers.
Say N has K digits. If we write a valid number with k digits (k < K), then there are (D\text{.length})^kpossible numbers we could write, since all of them will definitely be less than N.
Now, say we are to write a valid K digit number from left to right. For example, N = 2345, K = 4, and D = '1', '2', ..., '9'. Let's consider what happens when we write the first digit.
  • If the first digit we write is less than the first digit of N, then we could write any numbers after, for a total of (D\text{.length})^{K-1} valid numbers from this one-digit prefix. In our example, if we start with 1, we could write any of the numbers 1111 to 1999 from this prefix.
  • If the first digit we write is the same, then we require that the next digit we write is equal to or lower than the next digit in N. In our example (with N = 2345), if we start with 2, the next digit we write must be 3 or less.
  • We can't write a larger digit, because if we started with eg. 3, then even a number of 3000 is definitely larger than N.
Algorithm
Let dp[i] be the number of ways to write a valid number if N became N[i], N[i+1], .... For example, if N = 2345, then dp[0] would be the number of valid numbers at most 2345, dp[1] would be the ones at most 345, dp[2] would be the ones at most 45, and dp[3] would be the ones at most 5.
Then, by our reasoning above, dp[i] = (number of d in D with d < S[i]) * ((D.length) ** (K-i-1)), plus dp[i+1] if S[i] is in D.

  public int atMostNGivenDigitSet(String[] D, int N) {
    String S = String.valueOf(N);
    int K = S.length();
    int[] dp = new int[K + 1];
    dp[K] = 1;

    for (int i = K - 1; i >= 0; --i) {
      // compute dp[i]
      int Si = S.charAt(i) - '0';
      for (String d : D) {
        if (Integer.valueOf(d) < Si)
          dp[i] += Math.pow(D.length, K - i - 1);
        else if (Integer.valueOf(d) == Si)
          dp[i] += dp[i + 1];
      }
    }

    for (int i = 1; i < K; ++i)
      dp[0] += Math.pow(D.length, i);
    return dp[0];
  }


As in Approach #1, call a positive integer X valid if X <= N and X only consists of digits from D.
Now let B = D.length. There is a bijection between valid integers and so called "bijective-base-B" numbers. For example, if D = ['1', '3', '5', '7'], then we could write the numbers '1', '3', '5', '7', '11', '13', '15', '17', '31', ... as (bijective-base-B) numbers '1', '2', '3', '4', '11', '12', '13', '14', '21', ....
It is clear that both of these sequences are increasing, which means that the first sequence is a contiguous block of valid numbers, followed by invalid numbers.
Our approach is to find the largest valid integer, and convert it into bijective-base-B from which it is easy to find its rank (position in the sequence.) Because of the bijection, the rank of this element must be the number of valid integers.
Continuing our example, if N = 64, then the valid numbers are '1', '3', ..., '55', '57', which can be written as bijective-base-4 numbers '1', '2', ..., '33', '34'. Converting this last entry '34' to decimal, the answer is 16 (3 * 4 + 4).
Algorithm
Let's convert N into the largest possible valid integer X, convert X to bijective-base-B, then convert that result to a decimal answer. The last two conversions are relatively straightforward, so let's focus on the first part of the task.
Let's try to write X one digit at a time. Let's walk through an example where D = ['2', '4', '6', '8']. There are some cases:
  • If the first digit of N is in D, we write that digit and continue. For example, if N = 25123, then we will write 2 and continue.
  • If the first digit of N is larger than min(D), then we write the largest possible number from D less than that digit, and the rest of the numbers will be big. For example, if N = 5123, then we will write 4888 (4 then 888).
  • If the first digit of N is smaller than min(D), then we must "subtract 1" (in terms of X's bijective-base-B representation), and the rest of the numbers will be big.
    For example, if N = 123, we will write 88. If N = 4123, we will write 2888. And if N = 22123, we will write 8888. This is because "subtracting 1" from '', '4', '22' yields '', '2', '8' (can't go below 0).
Actually, in our solution, it is easier to write in bijective-base-B, so instead of writing digits of D, we'll write the index of those digits (1-indexed). For example, X = 24888 will be A = [1, 2, 4, 4, 4]. Afterwards, we convert this to decimal.
  • Time Complexity: O(\log N), and assuming D\text{.length} is constant.
  • Space Complexity: O(\log N), the space used by A. 
  public int atMostNGivenDigitSet(String[] D, int N) {
    int B = D.length; // bijective-base B
    char[] ca = String.valueOf(N).toCharArray();
    int K = ca.length;
    int[] A = new int[K];
    int t = 0;

    for (char c : ca) {
      int c_index = 0; // Largest such that c >= D[c_index - 1]
      boolean match = false;
      for (int i = 0; i < B; ++i) {
        if (c >= D[i].charAt(0))
          c_index = i + 1;
        if (c == D[i].charAt(0))
          match = true;
      }

      A[t++] = c_index;
      if (match)
        continue;

      if (c_index == 0) { // subtract 1
        for (int j = t - 1; j > 0; --j) {
          if (A[j] > 0)
            break;
          A[j] += B;
          A[j - 1]--;
        }
      }

      while (t < K)
        A[t++] = B;
      break;
    }

    int ans = 0;
    for (int x : A)
      ans = ans * B + x;
    return ans;

  }

https://zhanghuimeng.github.io/post/leetcode-902-numbers-at-most-n-given-digit-set/
数学方法
这是一种很神奇的方法。我们不妨把D中的数字看成是一种新的进位表示。比如，当D = {1, 3, 5}时，就可以把[11, 13, 51, 53]这类的数写成[11, 12, 31, 32]。如果能够知道<= N的最大的这种进位表示，就可以直接计算合法的数的数量了。所以剩下的问题就是怎么找到这个进位表示。
一种方法是根据N的位，从高位到低位分别进行讨论。令B表示所需的进位表示，1 <= B[i] <= D.size, 1 <= i <= len(N)：
  • 如果N[i] in D && N[i] = D[j]，则B[i] = j
  • 如果N[i] > min(D)，则B[i] = lower_bound(D, N[i])，B[i+1:] = len(D)，结束
  • 如果N[i] < min(D)，则B[i] = 0，并对之前的数执行类似于退位的操作，B[i+1:] = len(D)，结束
其他情况是比较显然的。一个需要退位的例子：D = {2, 4, 6, 8}，N = 41265
  1. B[1] = 2, "4"
  2. B[2] = 0；执行退位操作后，B[1] = 1, B[2] = 4, B[3:5] = 4, "28888"
找到这个进位表示之后就可以直接计算出比它小的数的数量了。事实上这种表示方法类似于Leetcode 171，同样没有0的位置。[1]
  • 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
    def atMostNGivenDigitSet(self, D, N):
        N = str(N)
        n = len(N)
        res = sum(len(D) ** i for i in range(1, n))
        i = 0
        while i < len(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)

https://leetcode.com/problems/numbers-at-most-n-given-digit-set/discuss/168313/Java-Solution-with-explanation

  1. Breaking the problem to finding the count of digits with exactly K digits. Iterating form K=1 to number of digits in N
  2. Now comes checking the count of K digits
    1. If number of digits is less than K, then answer is all possible permutations which would be Math.pow(D.length,K)
    2. If number of digits is 0 return 0
    3. If number of digits is exactly equal to K, then check the number of digits that can be formed by placing D[i] at highest position and count of K-1 digits.
    public int atMostNGivenDigitSet(String[] D, int N) {
        int result = 0;
        for(int i=1;i<=Integer.toString(N).length();i++){
            result += helper(D,i,Integer.toString(N));
        }
        return result;
    }
    
    //exactly N digit
    public int helper(String[] D, int K, String smax){
        if (smax.equals("0")) {
            return 0;
        }
        // String smax = Integer.toString(max);
        if(smax.length()>K){
            return (int)Math.pow(D.length,K);
        }
        int count=0;
        for(int i=0;i<D.length;i++){
            int char0 = Integer.parseInt(smax.charAt(0));
            if(Integer.parseInt(D[i])<char0){
                count += helper(D,K-1,smax);
            }
            if(Integer.parseInt(D[i])==char0){
                if (smax.length() > 1) {
                    int charRem = Integer.parseInt(smax.substring(1, 2)) == 0 ? 0 : Integer.parseInt(smax.substring(1));
                    count += helper(D, K - 1, Integer.toString(charRem));
                } else {
                    count++;
                }

            }
        }
        return count;
    }



Solution -1: DFS (TLE)
Time complexity: O(|D|^log10(N))

  int atMostNGivenDigitSet(vector<string>& D, int N) {
    int ans = 0;    
    dfs(D, 0, N, ans);
    return ans;
  }
private:
  void dfs(const vector<string>& D, int cur, int N, int& ans) {
    if (cur > N) return;
    if (cur > 0 && cur <= N) ++ans;
    for (const string& d : D)      
      dfs(D, cur * 10 + d[0] - '0', N, ans);    
  }

at
Labels: , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts