leetcode

commit 4fcdba0d6ecb25b0f3ac6b70de3109fce8c4b005
parent 1c894d773dd8205cb7ed12e88117d935b7cdb6ea
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu,  8 Feb 2024 20:07:49 +0000

1 Random Problem

Diffstat:
A
Problems/2397.cpp
 | 
31
+++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 32 insertions(+), 0 deletions(-)
diff --git a/Problems/2397.cpp b/Problems/2397.cpp
@@ -0,0 +1,31 @@
+class Solution {
+  public:
+    int maximumRows(const vector<vector<int>> &matrix, const int numSelect) const {
+        const int n = size(matrix), m = size(matrix[0]);
+        unordered_map<uint16_t, int> um;
+
+        for (int i = 0; i < n; i++) {
+            uint16_t crnt = 0, cnt = 0;
+            for (int j = 0; j < m; j++) {
+                crnt |= matrix[i][j] << j;
+                cnt += matrix[i][j];
+            }
+            if (cnt > numSelect) continue;
+            um[crnt]++;
+        }
+
+        uint16_t res = 0, crnt = (1 << numSelect) - 1;
+        while (crnt <= 1 << m) {
+            uint16_t count = 0;
+            for (const auto [k, v] : um) {
+                if ((k & ~crnt) == 0) count += v;
+            }
+            res = max(res, count);
+
+            uint16_t t = crnt | (crnt - 1);
+            crnt = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(crnt) + 1));
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1037,6 +1037,7 @@ for solving problems.
 |  2390  |   Medium   | [Removing Stars From a String](Problems/2390.cpp)                                                  |
 |  2391  |   Medium   | [Minimum Amount of Time to Collect Garbage](Problems/2391.cpp)                                     |
 |  2396  |   Medium   | [Strictly Palindromic Number](Problems/2396.cpp)                                                   |
+|  2397  |   Medium   | [Maximum Rows Covered by Columns](Problems/2397.cpp)                                               |
 |  2405  |   Medium   | [Optimal Partition of String](Problems/2405.cpp)                                                   |
 |  2410  |   Medium   | [Maximum Matching of Players With Trainers](Problems/2410.cpp)                                     |
 |  2414  |   Medium   | [Length of the Longest Alphabetical Continuous Substring](Problems/2414.cpp)                       |