leetcode

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 };