leetcode

commit 22247ab6a4848de2faeaae61b9290cc2d5787b7d
parent 7b10c7d04d0752b1776c6f58958966d9a2aaae3b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 28 Feb 2024 14:35:53 +0000

1 Random Problem

Diffstat:
A
Problems/2571.cpp
 | 
27
+++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 28 insertions(+), 0 deletions(-)
diff --git a/Problems/2571.cpp b/Problems/2571.cpp
@@ -0,0 +1,27 @@
+class Solution {
+    int rec(int n, int idx) const {
+        if (n == 0) return 0;
+        int res = INT_MAX, steps = 0;
+        for (int i = idx, mask = 1 << idx; n != 0 && i < 17; i++, mask <<= 1) {
+            if ((n & mask) == 0) continue;
+            res = min(res, 1 + rec(n - mask, i + 1) + steps);
+            n += mask, steps++;
+        }
+        return res;
+    }
+
+  public:
+    int minOperations(int n) const { return rec(n, 0); }
+};
+
+// Greedy
+class Solution {
+  public:
+    int minOperations(unsigned n) const {
+        int res = 0;
+        for (unsigned i = 0, mask = 1; i < 17; i++, mask <<= 1) {
+            if (popcount(n + mask) < popcount(n)) res++, n += mask;
+        }
+        return res + popcount(n);
+    }
+};
diff --git a/README.md b/README.md
@@ -1087,6 +1087,7 @@ for solving problems.
 |  2545  |   Medium   | [Sort the Students by Their Kth Score](Problems/2545.cpp)                                          |
 |  2551  |    Hard    | [Put Marbles in Bags](Problems/2551.cpp)                                                           |
 |  2568  |   Medium   | [Minimum Impossible OR](Problems/2568.cpp)                                                         |
+|  2571  |   Medium   | [Minimum Operations to Reduce an Integer to 0](Problems/2571.cpp)                                  |
 |  2579  |   Medium   | [Count Total Number of Colored Cells](Problems/2579.cpp)                                           |
 |  2592  |   Medium   | [Maximize Greatness of an Array](Problems/2592.cpp)                                                |
 |  2596  |   Medium   | [Check Knight Tour Configuration](Problems/2596.cpp)                                               |