aboutsummaryrefslogtreecommitdiff
path: root/min_one_bit_0.cpp
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
}