Try   HackMD

Count of ways to split a given number into prime segments

tags: Dynamic Programming, Amazon OA

Description:
Given numeric string str, the task is to count the number of ways the given string can be split, such that each segment is a prime number. Since the answer can be large, return the answer modulo 10^9 + 7.

Note: A split that contains numbers with leading zeroes will be invalid and the initial string does not contain leading zeroes.

Solution:

public class CountPrimeStrings { public int CountPrimeString(String str) { int n = str.length(); boolean[] sieve = buildSieve(); // dp[i]: # of ways to split substring(0, i) into primes long[] dp = new long[n + 1]; int mod = 1000000000 + 7; dp[0] = 1L; for (int i = 1; i <= n; i++) { for (int j = i - 1; j >= 0; j--) { String sub = str.substring(j, i); if (sub.startsWith("0")) continue; int num = Integer.parseInt(sub); if (sieve[num]) dp[i] += dp[j]; dp[i] %= mod; } } return (int)dp[n]; } private boolean[] buildSieve() { boolean[] sieve = new boolean[1000001]; sieve[0] = false; sieve[1] = false; for (int i = 0; i < sieve.length; i++) { sieve[i] = isPrime(i); } return sieve; } private boolean isPrime(int num) { if (num == 1) return false; int i = 2; while (i * i <= num) { if (num % i == 0) { return false; } i++; } return true; } }