Amazon Online Assessment 2021 (OA) - Split String Into Unique Primes
Imagine having a string of numbers, which can be any digit from 0 to 9. The task is to find out how many ways this string can be chopped into pieces where each piece represents a prime number. But not just any prime number; for a piece to count, it must be a prime number between 2 and 1000. Every single number in the string must be used up when creating these pieces.
But it's not as simple as it sounds; there are a few more rules! Firstly, each prime number, which we'll call pn, cannot start with a zero. That makes sense because in the world of numbers, leading zeros don't change the value of the number. Secondly, the prime number should always be within the boundaries of 2 and 1000. Just to remind, prime numbers are those numbers which can only be divided by 1 or themselves, but they must be greater than 1.
So, the big question here is: how many ways can the string of numbers be chopped up into these specific categories of prime numbers?
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]