r/algorithms • • 16d ago

Help Need help finding an efficient algorithm for modular divisibility with wildcards

Hi everyone!

I'm looking for help solving an algorithmic problem involving wildcard digits and modular arithmetic. I would really appreciate any hints, explanations, or suggestions for an efficient algorithm!

I've been thinking about this problem for a while, particularly about using dynamic programming over remainders, modular arithmetic, and possibly the Meet in the Middle technique.

Problem description

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.

Examples

Example 1

Input:

a = "4x"
b = 5

Output:

true

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

Example 2

Input:

a = "xx2"
b = 10

Output:

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 approach so far

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.

My questions

  1. Is there an efficient algorithm that avoids enumerating all possible remainders modulo b?

  2. Is there a mathematical observation that makes this problem simpler?

  3. What would be the optimal time and space complexity?

I'd be particularly interested in an explanation of the algorithm, rather than just code.

Any help, hints, or alternative approaches would be greatly appreciated. Thanks in advance!

1 Upvotes

11 comments sorted by

3

u/apnorton 16d ago

It's not my field of expertise and so I might be totally off-base here, but this sounds like you're trying to check whether there is a point on the lattice formed by ∑10kx_k ≡ 0 (mod b), where some of the x_k are known/concrete values, strictly within radius 10 of the origin under the L_∞ norm (i.e. max norm). If we were to allow the radius to possibly vary, this would be the decision problem for SVP, which is believed to be NP-hard.

Maybe fixing the radius to 10 would reduce the complexity, but I don't know of any algorithms off-hand... I'm doubting that you'd get much in the way of "efficient" solutions, but maybe checking to see if there's some extension of the LLL algorithm to other norms (since that's pretty constrained to the L_2 norm) could help get an approximation?

1

u/07734willy 16d ago

I also was thinking about framing this as SVP/CVP, but I’m not confident that LLL or BKZ would yield the true shortest/closest vector, especially in high dimensions. Still, could be worth finding a short vector and seeing if all components are <10 yielding a valid solution, as a quick early exit.

1

u/Interesting_Debate57 15d ago

The decision problem will be yes for most cases. Exponentially most.

The no cases will be sparse, so this is a sparse language. A decision problem with a sparse language.

I'll have to think about whether or not this is trivial.

2

u/FunSign5087 16d ago

Your example seems to imply that all wildcards 'x' must be replaced by the same number, then you can just brute force all 10 possibilities in O(1) time. I'm assuming this isn't the case and example could be improved :)

1

u/IronWombat15 16d ago

That's where I started, but "different occurrences of x can be replaced independently." The examples were misleading I think.

2

u/07734willy 16d ago

If the prime factorization of b contains 2s or 5s, you can implement some early-exit checks and constrain the lower digits of a to reflect those factors.

I think overall, the best approach is going to be using meet-in-the-middle, since a is so short (only 9 digits), it becomes very feasible. If all 9 digits are 'x' just return True (b itself is a solution), otherwise you have 8 or fewer 'x', meaning you can split it into two halves with 4 or fewer 'x'. Then brute force all the digits for 'x' in the first half, mod b, this will be at most 104 distinct values, store them in a hash table, then brute the second half the same way and query the hash table for -Y mod b (where Y is this half of the string a). If you find a hit, return True, else False. You won't need to store a full 1e9 size table, only the ~1e4 values in your hash table.

If b is prime there's some other tricks you could do mathematically to avoid storing those 1e4 values in a hash table (hinging on the fact that the product of all the possible a string assignments is 0 mod b if and only if one or more of them is itself 0 mod b), however that's much more complicated, and involves a lot of overhead computation on top of the 1e4 brute forcing itself.

3

u/IronWombat15 16d ago edited 16d ago

No hard answers here, just some musings.

My first thought is to decompose the problem to isolate the wildcards as a simplification.

Working an example:

a = "1x6", b = 11

Split a into 106 + x0

106 % 11 = 7

So now the question is, can any x satisfy x0 % 11 = (11 - 7) = 4?

  • 00 % 11 = 0

  • 10 % 11 = 10

  • 20 % 11 = 9

  • (Spot the pattern to jump to)

  • 70 % 11 = 4 (output true)

Minimal storage needs (potentially a 0-10 counter for each x). Brute forcing all possibly values of x would be O(10n) in the number of wildcards.

You can use dynamic programming to trade space for time, but a dynamic programming approach likely uses an array the size of your divisor.

In at least some cases, you can use modulus math to short circuit. (e.g xxxxxxxx1 % 100002 has no solution because every x produces even remainders, and no sum of evens will ever be odd. We can return false without iteration or dynamic programming.)

In the case where the answer is true though, I suspect you're forced to do a fair amount of computation. When the divisor is small, use DP. When the number of wildcards is small, brute force will still be fast. When both are large, you either find a mathematical shortcut, or spend a lot of time/space to solve.

As a practical matter though, given the constraints on length, even a brute force solution would likely have a short run time. Things become much more interesting if you allow for larger inputs.

(The general problem feels very knapsack coded, and I strongly suspect it's NP complete)

1

u/apnorton 16d ago

and I strongly suspect it's NP complete

This smells like lattice problems to me; I'd guess it shares difficulty with SVP, which is believed to be NP-hard.

1

u/bartekltg 16d ago

I haven't searched for a different solution, but you can salvager yours.

First, notice, you do not have to keep all possible reminders. * have not more than 10 reminders mod b. **** have no more than 10000 possible reminders. Use map/unorderedmap/dictionary/hashmap (whatever you prefer and how it is called in your language).

Second, do the meet in the middle trick. Calculate the possible reminders for the first half of the wildcards, then calculate the second set (remember it has to be multiplied by 10^k), then you can sort the sets and linearly (do you see why?) check, if there is a pair that gives 0.

10 000 is a good worst case, because if all 9 numbers are wildcards you just have to check if b fits into them. Otherwise you have at least one given number, and 8=2*4 wildcards.

0

u/[deleted] 16d ago

[deleted]

1

u/07734willy 16d ago

This ultimately leads to the same problem OP mentions with searching all residues mod b (up to 1e9), unless the number of x is small enough to just brute force anyway.

1

u/CranberryDistinct941 16d ago

Yeah I figured that out after I had it all typed out. Forgot I had already posted it and was editing it