aboutsummaryrefslogtreecommitdiff
path: root/other/min_one_bit_0.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/min_one_bit_0.cpp')
-rw-r--r--other/min_one_bit_0.cpp18
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
+}