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?


The input string does not contain any leading 0s.


Example 1:

Input: "31173"
Output: 6

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]

Try it yourself