2023-04-23 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 23

Description

Restore The Array

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.

Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only digits and does not contain leading zeros.
  • 1 <= k <= 109

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  const int MOD = 1e9 + 7;
  vector<int> dp;
  int solve(const string &s, int k, int pos) {
    if(pos == s.length()) return 1;
    if(s[pos] == '0') return 0;
    if(dp[pos] != -1) return dp[pos];
    int answer = 0;
    int num = 0;
    for(int j = pos; j < s.length(); ++j) {
      if((k - s[j] + '0') / 10 < num) break;
      num *= 10;
      num += s[j] - '0';
      answer += solve(s, k, j + 1);
      answer %= MOD;
    }

    return dp[pos] = answer;
  }
public:
  int numberOfArrays(string s, int k) {
    dp.resize(s.length(), -1);
    return solve(s, k, 0);
  }
};

// Accepted
// 83/83 cases passed (81 ms)
// Your runtime beats 45.35 % of cpp submissions
// Your memory usage beats 36.05 % of cpp submissions (20.8 MB)
Algorithm