Contents
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
- Shopping Patterns Solution Amazon OA 2023
- Reorder Data in Log Files Solution Amazon OA 2023
- Top K Frequent Words Solution Amazon OA 2023
- Trees Height Solution Amazon OA SDE 2023
- Counting Binary Substrings Amazon OA 2023
- Grid Connections Amazon OA 2023
- Shipment Imbalance Amazon OA 2023
- Max Profit Amazon OA 2023
- Find Lowest Price Amazon OA 2023
- Decode String Frequency Amazon OA 2023
- Simple Cipher Amazon OA 2023
- Valid Discount Coupons Amazon OA 2023 Solution
- Count Maximum Teams Amazon OA 2023
- Minimum Coin Flips Amazon OA 2023
- Max Average Stock Price Amazon OA 2023 Solution
- Robot Bounded In Circle Amazon OA 2023
- Shopping Options Amazon OA 2023 Solution
- Fill The Truck Maximum Units on a Truck Amazon OA Solution
- Maximize Score After N Operations Number Game Solution Amazon OA 2023
- Slowest Key Amazon OA 2023 Solution
- Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
- Storage Optimization Amazon OA 2023 Solution
- Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
- Autoscale Policy Utilization Check Amazon OA 2023
- Optimal Utilization Solution Amazon OA 2023
- Merge Two Sorted Lists Solution Amazon OA 2023
- Two Sum Unique Pairs Solution Amazon OA 2023
- Amazon Music Pairs Amazon OA 2023 Solution
- Class Grouping Amazon OA 2023 Solution
- Find Max products Amazon OA 2023 Solution
- Get encrypted number Amazon OA 2023 Solution
- Find Total Imbalance Amazon OA 2023 Solution
- Find Total Power Amazon OA 2023 Solution
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;
}
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;
}