Auto comment: topic has been updated by alpha_1001 (previous revision, new revision, compare).

Is the question complete or any missing information/wrong constraints? Because how will you check the 100000 digit number is prime or not in a fast way?

I don't know about this problem but whenever the problem ask about count number of ways I always struck don't get in what direction should I think can somebody suggest me some good problem (rating<= 1700), on this topic
btw cool alpha_1001 nice problem
thanks for your suggestion -is-this-fft- i will try to solve some problem and keeping these things in mind

Auto comment: topic has been updated by alpha_1001 (previous revision, new revision, compare).

Range DP. $$$dp[x]$$$ is the number of ways to split the number up until the $$$x$$$ part.

$$$dp[x] = \sum_{i = 1}^{7} dp[x - i] \text{ if the substring from x - i + 1 ... x is prime and in the range 2...1e6}.$$$

You can use DP to solve this where dp[i] is the number of ways to split the substring [i, N] into primes. Ans is dp[1].

For each i, iterate j through [0, 5] and check if the substring [i, i+j] is prime. If it is prime, add dp[i+j+1] to dp[i].

Checking if a substring is prime can be done quickly O(1) using sieve of eratosthenes precomputation.

Total complexity: O(6*N + Mlog(M)) where M = 10^6 and the second term is for the prime precomputation

from functools import lru_cache

def getPrimesUpTo(n):
    primes = set(range(2, n + 1))
    for i in range(2, n + 1):
        if i in primes:
            j = 2*i
            while j <= n:
                if j in primes:
                    primes.remove(j)
                j += i

    return primes

@lru_cache(None)
def helper(s, primes, i = 0, cur = None):
    # all primes that we split must be between 1 and 10**6
    if i == len(s):
        return 0 + (cur is None)

    cur = 0 if cur is None else cur
    cur = (cur * 10) + (ord(s[i]) - ord('0'))
    ret = 0
    if cur <= 10**6:
        ret += helper(s, primes, i + 1, cur)
    if cur in primes:
        ret += max(ret, helper(s, primes, i + 1, None))
    return ret % (10**9 + 7)

def countPrimeSplits(s):
    return helper(s, frozenset(getPrimesUpTo(10**6)))

Sieve to get the primes and apply DP to avoid redundant helper calls. The helper would be O(N^2) if not for the 10**6 limit, but it's more like O(N) with it.

I don't think frozenset is used very commonly — I definitely haven't used it before now — but it's useful in this case. I can't pass a regular set to that function because of the lru_cache decorator. It'd also be worth mentioning to the interviewer that we only have to run the sieve once before all of the function calls.

you have used the wrong abbreviation for MANGA, 100 social credit has been deducted from your account

Auto comment: topic has been updated by alpha_1001 (previous revision, new revision, compare).