A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 1521. Find a Value of a Mysterious Function Closest to Target, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: two pointers, bit manipulation.
The notes already sitting in the source point us in the right direction:
- https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/discuss/743146/Java-Straightforward-O(N2)-with-optimization
- time: O(N^2), space: O(1)
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 closestToTarget, sums.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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(nlog(max(arr)))
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/discuss/743146/Java-Straightforward-O(N2)-with-optimization
02//Runtime: 272 ms, faster than 94.55% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
03//Memory Usage: 61.7 MB, less than 100.00% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
04//time: O(N^2), space: O(1)
05class Solution {
06public:
07 int closestToTarget(vector<int>& arr, int target) {
08 int n = arr.size();
09 int res = INT_MAX;
10
11 for(int i = 0; i < n; ++i){
12 int sum = arr[i];
13 for(int j = i; j < n; ++j){
14 sum &= arr[j];
15 res = min(res, abs(sum-target));
16 if(res == 0) return res;
17 if(sum < target){
18 /*
19 in inner loop,
20 the more operations we do,
21 the smaller the "sum",
22 so if sum is already smaller than target,
23 we can just skip further operations
24 */
25 break;
26 }
27 }
28
29 if(sum > target){
30 /*
31 if sum > target,
32 than sum must be arr[i] & ... & arr[n-1]
33 (it completes the inner loop)
34
35 in outer loop,
36 when we increase i,
37 we will get larger "sum",
38 so we can just skip further calculation of "sum"
39 */
40 break;
41 }
42 }
43
44 return res;
45 }
46};
47
48//https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/discuss/743381/Python-6-lines-O(nlogm)-solution
49//Runtime: 1056 ms, faster than 46.01% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
50//Memory Usage: 193.9 MB, less than 100.00% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
51//time: O(nlog(max(arr)))
52class Solution {
53public:
54 int closestToTarget(vector<int>& arr, int target) {
55 int n = arr.size();
56 int ans = INT_MAX;
57 /*
58 at index j,
59 it contains
60 arr[0] & ... & arr[j],
61 arr[1] & ... & arr[j],
62 ...,
63 arr[j-1] & arr[j],
64 arr[j]
65
66 for these numbers,
67 arr[j] is the largest, and it takes log(arr[j]) bits.
68 If we look at bit representations,
69 arr[j-1] & arr[j] unset some '1's from arr[j],
70 and arr[j-2] & arr[j-1] & arr[j] unset more '1's in arr[j-1] & arr[j],
71 ..., and so on, since we have at most log(arr[j]) ones in arr[j],
72 so when we are at index j, the size of the set "sum" is O(log(arr[i]))
73
74 for all ending index j, the size of "sum" is then O(log(max(arr)))
75 */
76 set<int> sums;
77
78 for(int e : arr){
79 set<int> tmp;
80 transform(sums.begin(), sums.end(), inserter(tmp, tmp.end()),
81 [&e](int sum){return (sum & e);});
82 tmp.insert(e);
83 swap(tmp, sums);
84 for(int sum : sums){
85 ans = min(ans, abs(sum - target));
86 }
87 }
88
89 return ans;
90 }
91};
92
93//Binary search
94//https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/discuss/743267/C%2B%2B-O(N)-Algorithm-with-detailed-explanation-improved-from-O(N(log(N))
95//Runtime: 940 ms, faster than 55.42% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
96//Memory Usage: 141.9 MB, less than 100.00% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
97//time: O(NlogN)
98class Solution {
99public:
100 int closestToTarget(vector<int>& arr, int target) {
101 int n = arr.size();
102 int ans = INT_MAX;
103
104 const int maxbits = ceil(log2(1e6));
105 vector<vector<int>> bit2indices(maxbits);
106
107 for(int i = 0; i < n; ++i){
108 for(int b = 0; b < maxbits; ++b){
109 if(arr[i]>>b & 1){
110 //arr[i]'s bth bit is set
111 bit2indices[b].push_back(i);
112 }
113 }
114 }
115
116 /*
117 when index is i,
118 sums[i]: arr[i]
119 sums[i+1]: arr[i]&arr[i+1]
120 sums[i+2]: arr[i]&arr[i+1]&arr[i+2]
121 ...
122 sums[n-1]: arr[i]&...&arr[n-1]
123 */
124 vector<int> sums(n);
125
126 for(int i = n-1; i >= 0; --i){
127 //update sums[i+1], sums[i+2], ... sums[n-1]
128 for(int b = 0; b < maxbits; ++b){
129 if(!((arr[i]>>b)&1)){
130 /*
131 if arr[i]'s jth bit is unset
132 that means we need to
133 unset all arr[i+1...n-1]'s bth bit
134 */
135 while(!bit2indices[b].empty() && bit2indices[b].back() > i){
136 /*
137 bit2indices[b] is increasing,
138 so bit2indices[b].back() is the largest in bit2indices[b]
139 */
140
141 /*
142 sums[x]'s meaning changes from arr[i+1]&...&arr[n-1]
143 to arr[i]&arr[i+1]&...&arr[n-1],
144 i.e. sums[x] = sums[x] & arr[i],
145 we unset all sums[x]'s 1s bit by bit
146 */
147 sums[bit2indices[b].back()] -= 1<<b;
148 //After set this element's j'th bit to zero, we need not consider this bit again?
149 bit2indices[b].pop_back();
150 }
151 }
152 }
153 sums[i] = arr[i];
154
155 //sums[i...n-1] is decreasing
156 //binary search
157 int l = i, r = n;
158 int mid;
159 while(l < r){
160 mid = (l+r) >> 1;
161 if(sums[mid] == target){
162 return 0;
163 }else if(sums[mid] > target){
164 l = mid+1;
165 }else{
166 //sums[mid] > target
167 r = mid;
168 }
169 }
170
171 //?
172 if(l == n)ans = min(ans, abs(sums[n-1]-target));
173 else if(l == i)ans = min(ans, abs(sums[i]-target));
174 else ans = min({ans, abs(sums[l]-target), abs(sums[l -1]-target)});
175 }
176
177 return ans;
178 }
179};
180
181//O(N)
182//https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/discuss/743267/C%2B%2B-O(N)-Algorithm-with-detailed-explanation-improved-from-O(N(log(N))
183//Runtime: 932 ms, faster than 55.60% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
184//Memory Usage: 141.8 MB, less than 100.00% of C++ online submissions for Find a Value of a Mysterious Function Closest to Target.
185class Solution {
186public:
187 int closestToTarget(vector<int>& arr, int target) {
188 int n = arr.size();
189 int ans = INT_MAX;
190
191 const int maxbits = ceil(log2(1e6));
192 vector<vector<int>> bit2indices(maxbits);
193
194 for(int i = 0; i < n; ++i){
195 for(int b = 0; b < maxbits; ++b){
196 if(arr[i]>>b & 1){
197 bit2indices[b].push_back(i);
198 }
199 }
200 }
201
202 vector<int> sums(n);
203
204 /*
205 we want to find a 'r'
206 s.t. sums[r](arr[i]&...arr[r]) or
207 sums[r+1](arr[i]&...arr[r+1])
208 is closest to target
209 such r is decreasing for different i,
210 so actually we don't need binary search
211 */
212 int r = n-1;
213 for(int i = n-1; i >= 0; --i){
214 for(int b = 0; b < maxbits; ++b){
215 if(!((arr[i]>>b)&1)){
216 while(!bit2indices[b].empty() && bit2indices[b].back() > i){
217 sums[bit2indices[b].back()] -= 1<<b;
218 bit2indices[b].pop_back();
219 }
220 }
221 }
222 sums[i] = arr[i];
223
224 while(r > i && sums[r] < target) --r;
225 //now (1) sum[r] >= target and sum[r+1] < target or (2) r == i
226
227 ans = min({ans, abs(sums[r]-target),
228 (r != n-1) ? abs(sums[r+1]-target) : INT_MAX});
229 }
230
231 return ans;
232 }
233};Cost
Complexity
Time
O(nlog(max(arr)))
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.