Skip to content

1416. Restore The Array

SourceBiweekly Contest 24 Q4DifficultyHardRating1919

Description

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

Solutions

Solution 1

Thinking

We must split \(s\) into integers in \([1,k]\) with no leading zeros. \(n\le 10^5\) rules out enumerating cuts. \(k\le 10^9\), so a number starting at \(i\) spans at most \(10\) digits.

Let \(f(i)\) be the number of ways to restore \(s[i:]\). A leading zero dies; otherwise try end indices \(j\) while the value is \(\le k\) and add \(f(j+1)\). Memoize or compute right to left.

Compute \(f(i)\) from the right, with \(f(n)=1\). If \(s[i]\) is 0, then \(f(i)=0\). Otherwise extend a number from index \(i\) and stop once it exceeds \(k\), adding \(f(j+1)\) for every valid cut. The answer is \(f(0)\) modulo \(10^9+7\).

The time complexity is \(O(n \times d)\) and the space complexity is \(O(n)\), where \(n\) is the length of \(s\) and \(d\) is the number of decimal digits of \(k\), at most \(10\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod = 10**9 + 7
        n = len(s)
        f = [0] * (n + 1)
        f[n] = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue
            x = 0
            for j in range(i, n):
                x = x * 10 + int(s[j])
                if x > k:
                    break
                f[i] = (f[i] + f[j + 1]) % mod
        return f[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numberOfArrays(String s, int k) {
        final int mod = 1_000_000_007;
        int n = s.length();
        int[] f = new int[n + 1];
        f[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == '0') {
                continue;
            }
            long x = 0;
            for (int j = i; j < n; ++j) {
                x = x * 10 + s.charAt(j) - '0';
                if (x > k) {
                    break;
                }
                f[i] = (int) ((f[i] + f[j + 1]) % mod);
            }
        }
        return f[0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numberOfArrays(string s, int k) {
        const int mod = 1e9 + 7;
        int n = s.size();
        vector<int> f(n + 1);
        f[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '0') {
                continue;
            }
            long long x = 0;
            for (int j = i; j < n; ++j) {
                x = x * 10 + s[j] - '0';
                if (x > k) {
                    break;
                }
                f[i] = (f[i] + f[j + 1]) % mod;
            }
        }
        return f[0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func numberOfArrays(s string, k int) int {
    const mod = int(1e9 + 7)
    n := len(s)
    f := make([]int, n+1)
    f[n] = 1
    for i := n - 1; i >= 0; i-- {
        if s[i] == '0' {
            continue
        }
        x := 0
        for j := i; j < n; j++ {
            x = x*10 + int(s[j]-'0')
            if x > k {
                break
            }
            f[i] = (f[i] + f[j+1]) % mod
        }
    }
    return f[0]
}

Comments