diff options
Diffstat (limited to 'other/min_one_bit_0.cpp')
-rw-r--r-- | other/min_one_bit_0.cpp | 18 |
1 files changed, 18 insertions, 0 deletions
diff --git a/other/min_one_bit_0.cpp b/other/min_one_bit_0.cpp new file mode 100644 index 0000000..9820ace --- /dev/null +++ b/other/min_one_bit_0.cpp @@ -0,0 +1,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 +} |