Split String Into Unique Primes Solution Amazon OA 2021

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.

See Also : Amazon Online Assessment Questions 2021 Preparation

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 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 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 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;
}
}

Related:

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+