Minimum number X such that X % P == N

Question

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

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

Example :

3

52 100

11 100

51 1123

Output for given example :

52

-1

322352

Restrictions :

1 ≤ P ≤ 5 * 10^6

1 ≤ N ≤ P - 1

I attempted solving this problem by using a recursive function that would build numbers with digits from the given set and check if the condition is met, but that is way too slow because I have no idea when to stop searching (i.e. when there's no solution for the given tuple).

The author hints at using BFS somehow, but I really don't see any way to construct a meaningful graph using the input data of this problem.

How would you approach solving this problem?

Answer 1

You can solve this with a BFS, starting from 0, where adjacent vertices to a number n are 10n+2, 10n+3, 10n+5 and 10n+7. By keeping a record of all numbers mod p already queued, one can reduce the size of the search space, but more importantly know when the whole space has been searched.

Here's 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