leetcode

commit 5b66d3a36ebb5b96e69f6bf6047ca2706e4eb809
parent 0c4be2dd7e1849bf5f09add4e4952f5619fe1521
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  3 Nov 2024 23:15:16 +0100

Daily Problem, 1 Random

Diffstat:
A
Problems/0365.cpp
 | 
40
++++++++++++++++++++++++++++++++++++++++
A
Problems/0796.cpp
 | 
6
++++++
M
README.md
 | 
2
++

3 files changed, 48 insertions(+), 0 deletions(-)
diff --git a/Problems/0365.cpp b/Problems/0365.cpp
@@ -0,0 +1,40 @@
+// programming solution
+class Solution {
+    static int seen[1001][1001];
+
+    static bool rec(int x, int y, int target, int a = 0, int b = 0) {
+        if (a + b == target) return true;
+        if (seen[a][b]) return false;
+        seen[a][b] = true;
+
+        const int leftx = x - a;
+        const int lefty = y - b;
+
+        if (rec(x, y, target, x, b)) return true;
+        if (rec(x, y, target, a, y)) return true;
+        if (rec(x, y, target, 0, b)) return true;
+        if (rec(x, y, target, a, 0)) return true;
+        if (rec(x, y, target, a - min(a, lefty), b + min(a, lefty))) return true;
+        if (rec(x, y, target, a + min(b, leftx), b - min(b, leftx))) return true;
+
+        return false;
+    }
+
+  public:
+    bool canMeasureWater(int x, int y, int target) const {
+        memset(seen, 0x00, sizeof(seen));
+        return rec(x, y, target);
+    }
+};
+
+int Solution::seen[1001][1001];
+
+// Math solution: Bézout's identity
+class Solution {
+  public:
+    bool canMeasureWater(int x, int y, int target) const {
+        if (x + y < target) return false;
+        if (x == target || y == target || x + y == target) return true;
+        return target % gcd(x, y) == 0;
+    }
+};
diff --git a/Problems/0796.cpp b/Problems/0796.cpp
@@ -0,0 +1,6 @@
+class Solution {
+  public:
+    bool rotateString(const string &s, const string &goal) const {
+        return size(s) == size(goal) && (s + s).find(goal) != string::npos;
+    }
+};
diff --git a/README.md b/README.md
@@ -322,6 +322,7 @@ reference and a base for solving problems.
 |  0354  |    Hard    | [Russian Doll Envelopes](Problems/0354.cpp)                                                        |
 |  0355  |   Medium   | [Design Twitter](Problems/0355.cpp)                                                                |
 |  0357  |   Medium   | [Count Numbers with Unique Digits](Problems/0357.cpp)                                              |
+|  0365  |   Medium   | [Water and Jug Problem](Problems/0365.cpp)                                                         |
 |  0367  |    Easy    | [Valid Perfect Square](Problems/0367.cpp)                                                          |
 |  0368  |   Medium   | [Largest Divisible Subset](Problems/0368.cpp)                                                      |
 |  0371  |   Medium   | [Sum of Two Integers](Problems/0371.cpp)                                                           |
@@ -554,6 +555,7 @@ reference and a base for solving problems.
 |  0791  |   Medium   | [Custom Sort String](Problems/0791.cpp)                                                            |
 |  0792  |   Medium   | [Number of Matching Subsequences](Problems/0792.cpp)                                               |
 |  0795  |   Medium   | [Number of Subarrays with Bounded Maximum](Problems/0795.cpp)                                      |
+|  0796  |    Easy    | [Rotate String](Problems/0796.cpp)                                                                 |
 |  0797  |   Medium   | [All Paths From Source to Target](Problems/0797.cpp)                                               |
 |  0799  |   Medium   | [Champagne Tower](Problems/0799.cpp)                                                               |
 |  0802  |   Medium   | [Find Eventual Safe States](Problems/0802.cpp)                                                     |