The minimum number X is such that X% P == N

Question

This question is taken from the Romanian archive ACM-ICPC.

You are given T tuples of the form (N, P), find the smallest number X for each set such that X% P == N. If this is not possible, type -1. X can only be formed using numbers from the set {2, 3, 5, 7}.

Example:

3

52 100

11 100

51 1123

The output for this example:

52

one

322352

Limitations:

1 ≤ P ≤ 5 * 10 ^ 6

1 ≤ N ≤ P - 1

I tried to solve this problem using a recursive function that will build numbers with numbers from a given set and check if the condition is fulfilled, but it is too slow because I have no idea when to stop searching (i.e. when there is no solution for given tuple).

The author alludes to using BFS somehow, but I really see no way to build a meaningful graph using the input to this problem.

How do you approach the solution to this problem?

Answer 1

You can solve this with BFS starting at 0, where the neighboring vertices with number n are 10n + 2, 10n + 3, 10n + 5 and 10n + 7. By keeping a record of all mod p numbers already queued, you can reduce the size search space, but it’s more important to know when the entire space was searched.

Here is a simple Python implementation:

import collections def ns(n, p): q = collections.deque([0]) done = set() while q: x = q.popleft() for d in [2, 3, 5, 7]: nn = 10 * x + d if nn % p in done: continue if nn % p == n: return nn q.append(nn) done.add(nn % p) return -1 assert ns(52, 100) == 52 assert ns(11, 100) == -1 assert ns(51, 1123) == 322352 assert ns(0, 55) == 55