# Split String Into Unique Primes Amazon OA 2023

## Split String Into Unique Primes Solution

Given a string made up of integers 0 to 9, count the number of ways to split the string into prime numbers in the range of 2 to 1000 inclusive, using up all the characters in the string.

Each prime number, pn, must not contain leading 0s, and 2 <= pn <= 1000.

Constraints

The input string does not contain any leading 0s.

Examples

Example 1:

Input: “31173”

Output: 6

Explanation:

The string “31173” can be split into prime numbers in 6 ways:

• [3, 11, 7, 3]
• [3, 11, 73]
• [31, 17, 3]
• [31, 173]
• [311, 7, 3]
• [311, 73]

### SOLUTION

Program: Split String Into Unique Primes Solution in C++

``````#include<bits/stdc++.h>
using namespace std;
map<int,int> sieve(int n){
map<int,int> primes;
vector<int> p(1001,1);
p[0] = p[1] = 0;
for(int i = 2; i <= 1000; i++){
if(p[i] == 0)
continue;
for(int j = i*i; j <= 1000; j += i){
p[j] = 0;
}
}
for(int i = 2; i < 1000; i++){
if(p[i]){
primes[i] = 1;
}
}
return primes;
}
int solve(string &s, map<int,int> &prime){
int n = s.size();
int dp[n+1] = {0};	// dp[i] - number of ways to split till ith digit into primes
dp[0] = 1;

const int mod = 1e9 + 7;

for(int i = 1; i <= n; i++){

if(s[i-1] != '0' && prime[stoi(s.substr(i-1,1))])
dp[i] = dp[i-1];

if(i-2 >= 0 && s[i-2] != '0' && prime[stoi(s.substr(i-2,2))])
dp[i] = (dp[i] + dp[i-2]) % mod;

if(i-3 >= 0 && s[i-3] != '0' && prime[stoi(s.substr(i-3,3))])
dp[i] = (dp[i] + dp[i-3]) % mod;

}
return dp[n];
}
int main(){

// generate all primes till 1000
map<int,int> prime = sieve(1000);		// since 1000 is small you could also have done n*sqrt(n)
string s;
cin >> s;

cout << solve(s,prime) << endl;

return 0;
}``````

Program: Split String Into Unique Primes Solution in Python

``````def splitNum(s):
"""Split a string into all possible combinations"""
assert "," not in s
splits = []
i = 0
while i < 2 ** (len(s)-1):
b = str(bin(i))[2:]
b = "0" * (len(s)-len(b)-1) + b + "0"
p = 0
r = ""
while p < len(s):
r += s[p]
if b[p] == "1":
r += ","
p += 1
nums = [int(x) for x in r.split(",")]
splits.append(nums)
i += 1
return splits
def isPrime(n):
"""A really simplistic way of identifying a prime number"""
if n < 2:
return False
for i in range(2,n):
if (n % i == 0):
return False
return True
def areAllPrimes(s):
"""Return True if all numbers in the set are Prime numbers"""
for num in s:
if not isPrime(num):
return False
return True
s = "3175"
for splits in splitNum(s):
if areAllPrimes(splits):
print(splits)``````

Program: Split String Into Unique Primes Solution in Java

``````import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class PrimeNumber {
private Set map = new HashSet();
public static void main(String[] args) {
System.out.println(obj.findNumberOfWays("11373"));
System.out.println(obj.findNumberOfWays("3175"));
}
public int findNumberOfWays(String input) {
List<List<Integer>> ways = new ArrayList<>();
List<Integer> results = new ArrayList<Integer>();
findPermutations(input, results, ways);
return ways.size();
}
public void findPermutations(String suffix,
List<Integer> results, List<List<Integer>> resultSet) {

if (suffix.length() == 0) {
System.out.println(results.toString());
return;
}
for (int i = 0; i < suffix.length(); ++i) {
String snumber = suffix.substring(0, i + 1);
int numb = Integer.parseInt(snumber);
boolean isPrime = isPrimeNumber(numb);
if(isPrime){
findPermutations(suffix.substring(i + 1),	results, resultSet);
results.remove(results.size()-1);
}
}
}
public boolean isPrimeNumber(int number) {
if (map.contains(number)) {
return true;
}
boolean isPrime = isPrime(number);

return isPrime;
}
boolean isPrime(int n) {
if(n <= 1)
return false;
if(n == 2)	// 2 is prime
return true;
//check if n is a multiple of 2
if (n % 2 == 0)
return false;
//if not, then just check the odds
for(int i=3; i<=n/2; i=i+2) {
if(n % i == 0)
return false;
}
return true;
}
}``````

## Amazon OA 2023 Questions with Solution

### 2 thoughts on “Split String Into Unique Primes Amazon OA 2023”

1. As we have max 3 digit constraint, we don’t have to go over all permutations but can check one, two, and 3 digits at each location, checking remainders recursively. Once it is called with the index == length, we have one set of prime numbers. Like this (C#):

private static int GetNumPrimesSub(int[] numArr, int index)
{
if (index == numArr.Length)
{
return 1;
}

int primesCnt = 0;

if (IsPrime(numArr[index]))
{
primesCnt += GetNumPrimesSub(numArr, index + 1);
}

if (index < (numArr.Length – 1) && IsPrime(numArr[index] * 10 + numArr[index + 1]))
{
primesCnt += GetNumPrimesSub(numArr, index + 2);
}

if (index < (numArr.Length – 2) && IsPrime(numArr[index] * 100 + numArr[index + 1] * 10 + numArr[index + 2]))
{
primesCnt += GetNumPrimesSub(numArr, index + 3);
}

return primesCnt;
}

2. A better way is to use DP.

public int splitString(String s) {
int[] dp = new int[s.length() + 1];
dp[0] = 1;
for (int i = 1; i = 0 && j >= i – 3; j–) {
if (isPrime(s.substring(j, i))) {
dp[i] += dp[j];
}
}
}
return dp[dp.length – 1];
}
public boolean isPrime(String s) {
int num = Integer.parseInt(s);
if (num < 2) {
return false;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}