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) {
	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

  1. Shopping Patterns Solution Amazon OA 2023
  2. Reorder Data in Log Files Solution Amazon OA 2023
  3. Top K Frequent Words Solution Amazon OA 2023
  4. Trees Height Solution Amazon OA SDE 2023
  5. Counting Binary Substrings Amazon OA 2023
  6. Grid Connections Amazon OA 2023
  7. Shipment Imbalance Amazon OA 2023
  8. Max Profit Amazon OA 2023
  9. Find Lowest Price Amazon OA 2023
  10. Decode String Frequency Amazon OA 2023
  11. Simple Cipher Amazon OA 2023
  12. Valid Discount Coupons Amazon OA 2023 Solution
  13. Count Maximum Teams Amazon OA 2023
  14. Minimum Coin Flips Amazon OA 2023
  15. Max Average Stock Price Amazon OA 2023 Solution
  16. Robot Bounded In Circle Amazon OA 2023
  17. Shopping Options Amazon OA 2023 Solution
  18. Fill The Truck Maximum Units on a Truck Amazon OA Solution
  19. Maximize Score After N Operations Number Game Solution Amazon OA 2023
  20. Slowest Key Amazon OA 2023 Solution
  21. Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
  22. Storage Optimization Amazon OA 2023 Solution
  23. Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
  24. Autoscale Policy Utilization Check Amazon OA 2023
  25. Optimal Utilization Solution Amazon OA 2023
  26. Merge Two Sorted Lists Solution Amazon OA 2023
  27. Two Sum Unique Pairs Solution Amazon OA 2023
  28. Amazon Music Pairs Amazon OA 2023 Solution
  29. Class Grouping Amazon OA 2023 Solution
  30. Find Max products Amazon OA 2023 Solution
  31. Get encrypted number Amazon OA 2023 Solution
  32. Find Total Imbalance Amazon OA 2023 Solution
  33. Find Total Power Amazon OA 2023 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;
    }

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

    Reply

Leave a Comment

two × two =