blob: 9820acef276fee0090e7c4bacc1b74b593420a2c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include "leetcode.h"
class Solution {
public:
unordered_map<int, int> um{{0, 0}};
inline int bto0(int b) { return (1 << (b + 1)) - 1; }
int minimumOneBitOperations(int n) {
if (um.count(n))
return um[n];
int b = 31 - __builtin_clz(n);
return um[n] = bto0(b) - minimumOneBitOperations(n - (1 << b));
}
};
int main() {
Solution obj;
cout << obj.minimumOneBitOperations(39769175); // expect 4
}
|