Wildcard Digit Replacement

General Questions
#1

We are given a string a representing a non-negative integer and a positive integer b .

The string a consists of decimal digits (0–9 ) and wildcard characters (x ). Each occurrence of x can be independently replaced with any digit from 0 to 9 .

For example, x1x could become 212 , 010 , or 919 .

Our task is to determine whether there exists a replacement of all occurrences of x such that the resulting number:

  • Is divisible by b .

  • Is not equal to zero.

Leading zeros are allowed.

We need to return a Boolean value:

  • true if at least one valid replacement exists.

  • false otherwise.

A brute-force approach that tries every possible combination of digits is not considered optimal, since the number of combinations grows exponentially with the number of wildcards.

Examples

Example 1

Input:

text

a = "4x"
b = 5

Output:

text

true

Explanation: Replacing x with 0 gives 40 , which is divisible by 5 and is not zero.

Example 2

Input:

text

a = "xx2"
b = 10

Output:

text

false

Explanation: Every possible number ends in 2 , so none can be divisible by 10 .

Constraints

  • 1 <= len(a) <= 9

  • 1 <= b < 10^9

  • Leading zeros are allowed.

  • Different occurrences of x can be replaced independently.

My question

I suspect this problem can be solved using dynamic programming over possible remainders modulo b .

If the current prefix has remainder r , appending digit d gives:

python

new_remainder = (r * 10 + d) % b

However, a standard DP array of size b is impractical when b can be close to 10^9 .

Is there a more efficient approach that avoids enumerating all possible remainders or all combinations of wildcard digits?

I would appreciate an explanation of the optimal algorithm and its time and space complexity.