0 like 0 dislike
2,498 views

All past online assesments of Amazon can be found using the tag "amazon_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/amazon_oa

edited | 2,498 views

0 like 0 dislike
```// C++ implementation to count total
// number of ways to split a
// string to get prime numbers

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
bool sieve[1000000];

// Function to build sieve
void buildSieve()
{
for (auto& i : sieve)
i = true;

sieve[0] = false;
sieve[1] = false;

for (int p = 2; p * p <= 1000000;
p++) {

// If p is a prime
if (sieve[p] == true) {

// Update all multiples
// of p as non prime

for (int i = p * p; i <= 1000000;
i += p)
sieve[i] = false;
}
}
}

// Function to check whether a number
// is a prime number or not
bool isPrime(string number)
{
int num = stoi(number);
return sieve[num];
}

// Function to find the count
// of ways to split string
// into prime numbers
int rec(string& number, int i,
vector<int>& dp)
{
if (dp[i] != -1)
return dp[i];

int cnt = 0;

for (int j = 1; j <= 6; j++) {

// Number should not have a
// should be a prime number
if (i - j >= 0
&& number[i - j] != '0'
&& isPrime(
number.substr(i - j, j))) {

cnt += rec(
number, i - j, dp);
cnt %= MOD;
}
}
return dp[i] = cnt;
}

// Function to count the
// number of prime strings
int countPrimeStrings(string& number)
{
int n = number.length();
vector<int> dp(n + 1, -1);
dp[0] = 1;
return rec(number, n, dp);
}

// Driver code
int main()
{
buildSieve();

string s1 = "3175";

cout << countPrimeStrings(s1) << "\n";

return 0;
}
```
by Expert (113,040 points)
0 like 0 dislike

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]`
by Expert (113,040 points)