This problem looks busy at first, but the accepted solution is built around one steady invariant. For 902. Numbers At Most N Given Digit Set, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming.
The notes already sitting in the source point us in the right direction:
- DP
- time: O(log10(N)), space: O(log10(N))
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are atMostNGivenDigitSet, bijectoin.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(log10(N)), space: O(log10(N))
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DP
02//Runtime: 4 ms, faster than 40.00% of C++ online submissions for Numbers At Most N Given Digit Set.
03//Memory Usage: 8.3 MB, less than 18.52% of C++ online submissions for Numbers At Most N Given Digit Set.
04//time: O(log10(N)), space: O(log10(N))
05class Solution {
06public:
07 int atMostNGivenDigitSet(vector<string>& D, int N) {
08 string S = to_string(N);
09 int K = S.size();
10 //dp[i]: count of permutations starting from ith digit
11 vector<int> dp(K+1);
12
13 /*
14 edge case
15 for N = 123, D = ["1","3","5","7"],
16 when i = 2, Si is 3,
17 and when stoi(d) is "3",
18 we will add dp[K] to dp[K-1],
19 that means we are constructing x,
20 and x could be 3(one possible permutation)
21 */
22 dp[K] = 1;
23
24 for(int i = K-1; i >= 0; i--){
25 int Si = S[i] - '0';
26 for(string d : D){
27 // cout << "i: " << i << ", Si: " << Si << ", d: " << d << endl;
28 if(stoi(d) < Si){
29 /*
30 for N = 123, D = ["1","3","5","7"],
31 when i = 1, Si is 2,
32 and when stoi(d) is "1",
33 we are considerting 1x,
34 because 1 < 2, so x can be anything from D,
35 so we can construct 4 permutations: 11, 13, 15, 17
36 */
37 dp[i] += pow(D.size(), K-i-1);
38 // cout << "dp[" << i << "]: " << dp[i] << endl;
39 }else if(stoi(d) == Si){
40 /*
41 for N = 123, D = ["1","3","5","7"],
42 when i = 0, Si is 1,
43 and when stoi(d) is "1",
44 we are constructing 1xx,
45 for the last 2 digits,
46 we can just use what we have got from i=1 th digit
47 (11, 13, 15, 17),
48 and build 111, 113, 115, 117
49 */
50 dp[i] += dp[i+1];
51 // cout << "dp[" << i << "]: " << dp[i] << endl;
52 }/*else if(stoi(d) > Si){
53 //we cannot construct a number in this case!
54 }*/
55 }
56 }
57
58 for(int i = 1; i < K; i++){
59 /*
60 say N has K digits,
61 here we are counting the permutations of D to form a i-digit number,
62 i ranges from 1 to K-1
63
64 for N = 123, D = ["1","3","5","7"]
65 1-digit permutation:
66 1,3,5,7
67 2-digit permutation:
68 11,13,15,17,31,33,35,37,51,53,55,57,71,73,75,77
69 */
70 dp[0] += pow(D.size(), i);
71 // cout << "i: " << i << ", dp[0]: " << dp[0] << endl;
72 }
73
74 return dp[0];
75 }
76};
77
78//Math
79//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Numbers At Most N Given Digit Set.
80//Memory Usage: 8.2 MB, less than 41.15% of C++ online submissions for Numbers At Most N Given Digit Set.
81//time: O(log10(N)), space: O(log10(N))
82class Solution {
83public:
84 int atMostNGivenDigitSet(vector<string>& D, int N) {
85 string S = to_string(N);
86 int K = S.size();
87 //1-based
88 //bijectoin is the bijection representation of largest number that <= N
89 vector<int> bijectoin(K);
90 int t = 0;
91
92 for(char c : S){
93 // cout << "c: " << c << endl;
94 int c_index = 0;
95 bool match = false;
96 for(int i = 0; i < D.size(); i++){
97 if(c-'0' >= stoi(D[i])){
98 c_index = i+1;
99 }
100 if(c-'0' == stoi(D[i])){
101 match = true;
102 }
103 }
104
105 // cout << D[t] << " -> " << c_index << endl;
106 // cout << "match: " << match << endl;
107 /*
108 c_index is the index in D(1-based) pointing to
109 a number just <= c
110 c_index may be 0(it's invalid value)
111 */
112 bijectoin[t++] = c_index;
113 /*
114 if we can find c in D,
115 we just map current char in S to i+1(1-based)
116 and move forward
117 */
118 if(match) continue;
119
120 if(c_index == 0){
121 /*
122 that means we cannot find a c >= all D[i],
123 i.e. c is smaller than all D[i],
124 so we need to subtract 1
125
126 j starts from t-1: because we want to overwrite
127 previous bijection[t]
128
129 j ends at 1: because we will use bijection[j-1]
130 */
131 for(int j = t-1; j > 0; j--){
132 //?
133 if(bijectoin[j] > 0) break;
134 // bijectoin[j] += D.size();
135 bijectoin[j] = D.size();
136 bijectoin[j-1]--;
137 // cout << D[j] << " -> " << bijectoin[j] << endl;
138 // cout << D[j-1] << " -> " << bijectoin[j-1] << endl;
139 }
140 }
141
142 /*
143 D = ['2', '4', '6', '8'], N = 5123
144 c_index will be 2 for the most significant digit 5,
145 we want bijection become 2444(represents for 4888)
146 */
147 while(t < K){
148 // cout << D[t] << " -> " << D.size() << endl;
149 bijectoin[t++] = D.size();
150 }
151 break;
152 }
153
154 /*
155 convert base-(D.size()) positional notation
156 to base-10 position notation
157 */
158 int ans = 0;
159
160 for(int e : bijectoin){
161 ans = ans * D.size() + e;
162 // cout << "e: " << e << ", ans: " << ans << endl;
163 }
164
165 return ans;
166 }
167};Cost
Complexity
Time
O(log10(N)), space: O(log10(N))
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.