The trick here is to name the state correctly, then let the implementation follow. For 964. Least Operators to Express Number, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. 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: DFS + memoization, graph traversal, dynamic programming, greedy.
The notes already sitting in the source point us in the right direction:
- TLE
- 1 / 159 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are evaluate, opds, leastOpsExpressTarget, dfs.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- 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:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//1 / 159 test cases passed.
03class Solution {
04public:
05 int x;
06 int minOps;
07 int target;
08 vector<char> ops = {'+', '-', '*', '/'};
09
10 int evaluate(string oprs){
11 vector<int> opds(oprs.size()+1, x);
12
13 // for(int i = 0; i < oprs.size(); ++i){
14 // cout << opds[i] << oprs[i];
15 // }
16 // cout << opds[oprs.size()] << endl;
17
18 for(int i = 0; i < oprs.size(); ++i){
19 // cout << "oprs: " << oprs.size() << ", opds: " << opds.size() << endl;
20 if(oprs[i] == '*'){
21 opds[i] *= opds[i+1];
22 opds.erase(opds.begin()+i+1);
23 oprs.erase(oprs.begin()+i);
24 }else if(oprs[i] == '/'){
25 opds[i] /= opds[i+1];
26 opds.erase(opds.begin()+i+1);
27 oprs.erase(oprs.begin()+i);
28 }
29 }
30
31 int res = opds[0];
32
33 for(int i = 0; i < oprs.size(); ++i){
34 if(oprs[i] == '+'){
35 res += opds[i+1];
36 }else if(oprs[i] == '-'){
37 res -= opds[i+1];
38 }
39 }
40
41 // cout << "res: " << res << endl;
42 return res;
43 };
44
45 int leastOpsExpressTarget(int x, int target) {
46 minOps = INT_MAX;
47 this->x = x;
48 this->target = target;
49 ops = {'+', '-', '*', '/'};
50
51 string expr;
52 queue<string> q;
53 unordered_set<string> visited;
54
55 q.push("");
56 visited.insert("");
57
58 while(!q.empty()){
59 expr = q.front(); q.pop();
60
61 int res = evaluate(expr);
62
63 if(res == target){
64 break;
65 }else if(res < target){
66 for(char op : {'+', '*'}){
67 if(visited.find(expr+op) == visited.end()){
68 visited.insert(expr+op);
69 q.push(expr+op);
70 }
71 }
72 }else{
73 for(char op : {'-', '/'}){
74 if(visited.find(expr+op) == visited.end()){
75 visited.insert(expr+op);
76 q.push(expr+op);
77 }
78 }
79 }
80 }
81
82 return expr.size();
83 }
84};
85
86//recursion, greedy
87//https://leetcode.com/problems/least-operators-to-express-number/discuss/208445/c%2B%2B-recursive-easy-to-understand
88//Runtime: 44 ms, faster than 33.96% of C++ online submissions for Least Operators to Express Number.
89//Memory Usage: 6 MB, less than 83.96% of C++ online submissions for Least Operators to Express Number.
90class Solution {
91public:
92 int leastOpsExpressTarget(int x, int target) {
93 if(x == target){
94 return 0;
95 }else if(x > target){
96 /*
97 if x = 3 and target = 2,
98 (1) by adding: 3/3+3/3=2, need "target" '/' and "target-1" '+'
99 (2) by subtracting: 3-3/3=2, need "target-x" '-' and '/'
100 */
101 return min(2*target-1, 2*(x-target));
102 }else{
103 //x < target
104 long long cur = x;
105 int count = 0;
106
107 //greedy, use '*' as many as possible
108 while(cur < target){
109 cur *= x;
110 ++count;
111 }
112
113 if(cur == target){
114 return count;
115 }
116
117 //cur > target
118 int sub_count = INT_MAX, add_count = INT_MAX;
119
120 /*
121 x = 3, target = 5, cur = 9
122 9-5=4, 4 is the new target
123 */
124 if(cur - target < target){ //?
125 sub_count = count + leastOpsExpressTarget(x, cur-target);
126 }
127
128 /*
129 x = 3, target = 5, cur = 9
130 5-9/3=2, 2 is the new target
131 we fall back to cur/x, so count-1
132 */
133 add_count = count - 1 + leastOpsExpressTarget(x, target-cur/x);
134
135 //+1: current expression need to be concatenated(+/-) with the previous one
136 return min(sub_count, add_count) + 1;
137 }
138 }
139};
140
141//improved from above, dfs + memorization
142//Runtime: 8 ms, faster than 73.58% of C++ online submissions for Least Operators to Express Number.
143//Memory Usage: 12.2 MB, less than 8.49% of C++ online submissions for Least Operators to Express Number.
144class Solution {
145public:
146 unordered_map<int, int> memo;
147
148 int dfs(int x, int target) {
149 if(memo.find(target) != memo.end()){
150 return memo[target];
151 }else if(x == target){
152 return memo[target] = 0;
153 }else if(x > target){
154 return memo[target] = min(2*target-1, 2*(x-target));
155 }else{
156 //x < target
157 long long cur = x;
158 int count = 0;
159
160 while(cur < target){
161 cur *= x;
162 ++count;
163 }
164
165 if(cur == target){
166 return memo[target] = count;
167 }
168
169 int sub_count = INT_MAX, add_count = INT_MAX;
170
171 if(cur - target < target){ //?
172 sub_count = count + dfs(x, cur-target);
173 }
174
175 add_count = count - 1 + dfs(x, target-cur/x);
176
177 return memo[target] = min(sub_count, add_count) + 1;
178 }
179 }
180
181 int leastOpsExpressTarget(int x, int target) {
182 return dfs(x, target);
183 }
184};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
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.