leetcode

commit 0024d5569ebe626647ca76e2abcfbca6518e3284
parent 70656d2236524f7148831eb27ce1e6a670bd4358
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 19 Oct 2023 14:55:31 +0000

Random Problem

Diffstat:
A
Problems/2698.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/2698.cpp b/Problems/2698.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  public:
+    bool canPartition(const string &s, const int target) {
+        if (s == "" && target == 0) return true;
+        if (target < 0) return false;
+
+        int left = 0;
+        for (int i = 0; i < s.size(); i++) {
+            left = left * 10 + s[i] - '0';
+            if (canPartition(s.substr(i + 1), target - left)) return true;
+        }
+        return false;
+    }
+
+    int punishmentNumber(int n) {
+        int res = 0;
+        for (int i = 1; i <= n; i++) {
+            const int sqr = i * i;
+            if (canPartition(to_string(sqr), i)) res += sqr;
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -866,6 +866,7 @@ for solving problems.
 |  2676  |   Medium   | [Throttle](Problems/2676.js)                                                                       |
 |  2683  |   Medium   | [Neighboring Bitwise XOR](Problems/2683.cpp)                                                       |
 |  2685  |   Medium   | [Count the Number of Complete Components](Problems/2685.cpp)                                       |
+|  2698  |   Medium   | [Find the Punishment Number of an Integer](Problems/2698.cpp)                                      |
 |  2707  |   Medium   | [Extra Characters in a String](Problems/2707.cpp)                                                  |
 |  2711  |   Medium   | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp)                          |
 |  2740  |   Medium   | [Find the Value of the Partition](Problems/2740.cpp)                                               |