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 10⁹ + 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 <= 10⁵
s consists of only digits and does not contain leading zeros.
1 <= k <= 10⁹

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(nd)\), 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\).

Python3JavaC++Go

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]

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];
    }
}

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];
    }
};

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]
}

Solution 2: Rolling Dynamic Programming

Thinking

Solution 1 stores a value for every suffix, although a number starting at a position can use at most \(d\) digits, where \(d\) is the number of digits in \(k\). While scanning from right to left, the next state therefore reads only the following \(d\) suffix counts. We can keep those counts in a circular array of length \(d+1\): the slot for the current position cannot overlap any slot that it still needs to read. This preserves the same transitions while removing the \(O(n)\) DP array.

Let \(f(i)\) be the number of valid partitions of \(s[i:]\), with \(f(n)=1\). If \(s[i]\) is 0, then \(f(i)=0\). Otherwise, extend the first number by at most \(d\) digits; for every value at most \(k\), add \(f(j+1)\) modulo \(10^9+7\).

Store \(f(i)\) at index \(i \bmod (d+1)\). Every value read while computing \(f(i)\) has an index in \([i+1,i+d]\), so none shares the slot for \(i\). The time complexity is \(O(nd)\), as in Solution 1, while the auxiliary space drops from \(O(n)\) to \(O(d)\); here \(d\le 10\).

Python3C++TypeScript

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod = 10**9 + 7
        n = len(s)
        d = len(str(k))
        f = [0] * (d + 1)
        f[n % (d + 1)] = 1
        for i in range(n - 1, -1, -1):
            ways = 0
            if s[i] != '0':
                value = 0
                for j in range(i, min(n, i + d)):
                    value = value * 10 + int(s[j])
                    if value > k:
                        break
                    ways = (ways + f[(j + 1) % (d + 1)]) % mod
            f[i % (d + 1)] = ways
        return f[0]

class Solution {
public:
    int numberOfArrays(string s, int k) {
        constexpr int mod = 1e9 + 7;
        int n = s.size(), d = to_string(k).size();
        vector<int> f(d + 1);
        f[n % (d + 1)] = 1;
        for (int i = n - 1; i >= 0; --i) {
            int ways = 0;
            if (s[i] != '0') {
                long long value = 0;
                for (int j = i; j < n && j < i + d; ++j) {
                    value = value * 10 + s[j] - '0';
                    if (value > k) break;
                    ways = (ways + f[(j + 1) % (d + 1)]) % mod;
                }
            }
            f[i % (d + 1)] = ways;
        }
        return f[0];
    }
};

function numberOfArrays(s: string, k: number): number {
    const mod = 1e9 + 7;
    const n = s.length;
    const d = String(k).length;
    const f = Array(d + 1).fill(0);
    f[n % (d + 1)] = 1;
    for (let i = n - 1; i >= 0; --i) {
        let ways = 0;
        if (s[i] !== '0') {
            let value = 0;
            for (let j = i; j < n && j < i + d; ++j) {
                value = value * 10 + s.charCodeAt(j) - 48;
                if (value > k) {
                    break;
                }
                ways = (ways + f[(j + 1) % (d + 1)]) % mod;
            }
        }
        f[i % (d + 1)] = ways;
    }
    return f[0];
}

1416. Restore The Array

Description

Solutions

Solution 1

Solution 2: Rolling Dynamic Programming

Comments