leetcode

commit 1cd4ccce3e5f30b0c175c48e7ecd7779b3df2226
parent e4884434eca0a56ae251c262f5a482a81572abbe
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 23 Apr 2023 20:04:25 +0200

Daily Problem

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

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/1416.cpp b/Problems/1416.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  static const int mod = 1E9 + 7;
+  static const int size = 1E5 + 1;
+  int dp[size];
+
+public:
+  Solution() { memset(dp, 0xFF, sizeof(dp)); }
+
+  int numberOfArrays(const string &s, int k, int crnt = 0) {
+    if (crnt >= s.size()) return 1;
+    if (s[crnt] == '0') return 0;
+    if (dp[crnt] != -1) return dp[crnt];
+
+    long long num = 0, res = 0;
+    for (int i = crnt; i < s.size(); i++) {
+      num = num * 10 + (s[i] - '0');
+      if (num > k) break;
+      res = (res + numberOfArrays(s, k, i + 1)) % mod;
+    }
+
+    return dp[crnt] = res;
+  }
+};
diff --git a/README.md b/README.md
@@ -520,4 +520,5 @@ for solving problems.
 |  2477  |   Medium   | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp)                                  |
 |  2492  |   Medium   | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp)                                  |
 |  2497  |   Medium   | [Maximum Star Sum of a Graph](Problems/2497.cpp)                                                 |
+|  1416  |    Hard    | [Restore The Array](Problems/1416.cpp)                                                           |