Numbers In Pi

Tags

Numbers In Pi

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given a string of digits representing pi (e.g., "3141592653...") and a list of favorite numbers (as strings), determine the minimum number of spaces that can be inserted into the pi string so that every resulting segment is one of the favorite numbers. Return -1 if it is impossible.

Intuition

This is a string segmentation problem (similar to Word Break). At each position in the pi string, we try every favorite number that matches a prefix starting at that position. If a number matches, we jump ahead by its length and solve the remaining suffix. Overlapping subproblems arise because multiple numbers may lead to the same suffix start position. DP (or memoization) eliminates redundant work.

Approach

  1. Store all favorite numbers in a hash set for O(1) lookups.
  2. Create an array dp of size n+1 (where n = len(pi)), initialized to infinity. Set dp[n] = -1 (no spaces needed after the last character — we use -1 because the first matched segment does not add a space).
  3. Iterate i from n-1 down to 0:
    • For each j from i+1 to n:
      • If pi[i..j] is in the set and dp[j] is not infinity:
        • dp[i] = min(dp[i], dp[j] + 1)
  4. Return dp[0] if it is not infinity, otherwise -1.

Pseudocode

function numbersInPi(pi, numbers):
    numberSet = set(numbers)
    n = length(pi)
    dp = array of size (n+1), filled with INFINITY
    dp[n] = -1

    for i from n-1 down to 0:
        for j from i+1 to n:
            substring = pi[i..j]
            if substring in numberSet and dp[j] != INFINITY:
                dp[i] = min(dp[i], dp[j] + 1)

    return dp[0] if dp[0] != INFINITY else -1

Time & Space Complexity

MeasureComplexityJustification
TimeO(n^2 * m)n positions, up to n substring lengths, substring hashing up to length m (max number length). Using a trie reduces this.
SpaceO(n + k)DP array of size n, plus storage for the number set of total size k

Key Insights

  • Using a trie built from the favorite numbers lets you scan forward from each position i character by character, pruning early when no number shares the current prefix. This can significantly reduce the inner loop.
  • The +1 in the recurrence counts one space inserted between the current segment and the rest; dp[n] = -1 offsets this so the total equals the number of spaces, not segments.
  • This is essentially the Word Break problem with an optimization objective (minimize spaces rather than just checking feasibility).

Edge Cases

  • Pi string is empty: return -1 (or 0 depending on convention).
  • No favorite numbers provided: impossible, return -1.
  • Pi string is itself one favorite number: return 0 (no spaces needed).
  • Favorite numbers that overlap: e.g., "314" and "31" and "4" — DP naturally considers all valid decompositions.
  • Very long pi string: O(n^2) may be tight; trie optimization is important in practice.

Linked mentions