alpha_1001's blog

Help in this Counting Problem. Was asked in one of the FAANG OA.
By alpha_1001, history, 3 years ago, In English 
Given a string **S** consisting of digits [0-9], count the number of ways this string can be split into continuous substrings such that each substring is a prime number. Each digit must be in one substring and the entire string must be used.

**Note:**
The input string does not contain leading zeros.
Each number split of the given number must be in the range `2 to 1e6` inclusive.
Since the answer can be large, return the answer modulo `1e9+7`.


**Constraints**
1 <= | S | <= 1e5

**Example**
_input_
11373
_output_
6
_Explanation_
[11, 3, 7, 3], [11, 3, 73], [11, 37, 3], [113, 7, 3], [113, 73], [11, 373].


Can anyone help me out?
Thanks in advance.
Happy Coding...
 
P.S.: This is my first blog, so correct me if I'm wrong anywhere.

Feel free to share your approach.

  • Vote: I like it
  • -24
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    "Count number of ways" is too broad, so it is really hard for anyone to suggest something.

    But being very comfortable with dynamic programming is always useful in such problems. In easier cases, the following will often solve the problem: let dp[i] be the number of ways to do something if we only consider the first i characters of the string (string can be replaced with whatever). Another thing that will help a lot is understanding the first principles of combinatorics: factorials, number of combinations and the like (not in this problem though).

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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}.$$$

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it 
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.

→ Reply
»
3 years ago, # |
  Vote: I like it +65 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It would have been great if you had helped me solve the above problem instead of looking at MANGA, MAANG, FAANG,... . I solved it though.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply