Count the Ways to Split a Digit String into Primes

Question

The question asks the candidate to determine the number of ways to split a given digit string into valid prime numbers.

Codemia · Accepted Answer

To solve the problem of counting ways to split a digit string into primes, we can use a recursive approach combined with dynamic programming. The idea is to explore all possible splits of the string and check if the resulting substrings are prime numbers. We will maintain a memoization table to store results of previously computed splits to avoid redundant calculations.

1. Create a helper function `is_prime(num)` that checks if a number is prime.
2. Define a recursive function `count_ways(start)` that counts valid splits starting from the index `start`.
3. In `count_ways`, iterate through the string from `start` to the end, creating substrings and checking if they are prime.
4. If a substring is prime, recursively call `count_ways` for the next index after the substring.
5. Use memoization to store results of `count_ways(start)` to optimize performance.

The time complexity of this approach is O(n * 2^n) in the worst case due to the number of possible splits, but with memoization, it can be significantly reduced. The space complexity is O(n) for the memoization table.

```python
def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def count_ways(s):
    memo = {}  
    def helper(start):
        if start == len(s):
            return 1
        if start in memo:
            return memo[start]
        count = 0
        for end in range(start + 1, len(s) + 1):
            num = int(s[start:end])
            if is_prime(num):
                count += helper(end)
        memo[start] = count
        return count
    return helper(0)

# Example usage:
print(count_ways('233'))  # Output: 2 (2, 3 and 23, 3)
```

In summary, this problem requires a combination of string manipulation and prime number checking. By using recursion and memoization, we can efficiently count the number of ways to split the digit string into valid prime numbers. This approach not only solves the problem but also demonstrates a solid understanding of algorithm design.

Count the Ways to Split a Digit String into Primes

Salesforce

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Salesforce Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string