Split String Into Unique Primes Amazon OA 2023

Contents

1 Split String Into Unique Primes Solution
- 1.1 SOLUTION
2 Amazon OA 2023 Questions with Solution

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) {
	PrimeNumber obj = new PrimeNumber();
	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) {
		resultSet.add(new ArrayList<Integer>(results));
		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){
			results.add(numb);
			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);
	if(isPrime) map.add(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”

shilta
March 21, 2022 at 7:53 am
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;
}
Frodo
June 8, 2022 at 8:42 pm
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;
}

Split String Into Unique Primes Solution

SOLUTION

Amazon OA 2023 Questions with Solution

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

Leave a Comment Cancel reply