leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2571.cpp (733B)

      1 class Solution {
      2     int rec(int n, int idx) const {
      3         if (n == 0) return 0;
      4         int res = INT_MAX, steps = 0;
      5         for (int i = idx, mask = 1 << idx; n != 0 && i < 17; i++, mask <<= 1) {
      6             if ((n & mask) == 0) continue;
      7             res = min(res, 1 + rec(n - mask, i + 1) + steps);
      8             n += mask, steps++;
      9         }
     10         return res;
     11     }
     12 
     13   public:
     14     int minOperations(int n) const { return rec(n, 0); }
     15 };
     16 
     17 // Greedy
     18 class Solution {
     19   public:
     20     int minOperations(unsigned n) const {
     21         int res = 0;
     22         for (unsigned i = 0, mask = 1; i < 17; i++, mask <<= 1) {
     23             if (popcount(n + mask) < popcount(n)) res++, n += mask;
     24         }
     25         return res + popcount(n);
     26     }
     27 };