leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2571.cpp (733B)

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