Shortest number divisible by number M

Question

I'm working on one algorithm and I'd appreciate some maths help. I'm not truly sure if it is maths problem exactly or it's just some data structure to use and problem will be solved. On input you got number M and number N (divided by space); and after N there is N digits (0 - 9). The problem is to find a shortest number you can create from these digits that will be divisible by your M number. For example input:

7 2 1 3

outputs:

133

simply because 133 (and only digits that can be used are 1 and 3) is divisible by 7 and it's the shortest number divisible by 7. Actually, the number doesn't need to be lowest, just the shortest. If there is no number that can be made from such digits, print -1. Thanks in advance if there is some genius mathematician :P

EDIT: There is no space limitation but the time limit should be 10seconds for any input, no matter Big-O.

Answer 1

You could do it by using modular arithmetic to search for solutions one digit at a time

We can think of this problem as finding a sequence of n digits d_i ∈S such that

If we do all our arithmetic mod m, we can think about it as a search for a path to the value "0" over the space of integers modulo m. Each step in the search is computed by appending an additional digit to our number. Horner's Method tells us that

Which means that for each digit we append to the number, we are multiplying the old value by 10, and adding the value of the new digit. Multiplication by 10 and addition of the digit are both easy to do mod m, and so we as we build up the number one digit at a time, we can keep track of its value mod m. The steps along the construction of the number trace out a "path" through the nodes based on the values mod 10 it reaches.

We will just perform a graph search on these paths to find the shortest "path" to (0). So for each step of the graph search, we compute the shortest "path" of length i (i.e. the smallest number with i digits) which ends on a given "node" (i.e. a value mod m).

So for example, let's imagine our digit set is {1,3} and m=9. Then our set of nodes for the search is going to be {(0),(1),...,(8)}. For each node, we store the "best path so far" to reach it. This simply means that for node (k), we store the smallest number we have found so far which equals k mod m.

At the first step in the search, we want to find the smallest 1 digit number which is equal to each value from 0,1,...,8 mod 9. Because our only available digits are 1 and 3, (1) and (3) are the only reachable nodes on the first step, and all other nodes are unreachable.

On the second step, we are trying to find the smallest two digit number which is equal to each value from 0,1,...,8 mod 9. From Horner's method, we remember that every two digit number is just 10*p + d where p is a 1-digit number. So we can get all of the nodes reachable in two steps by taking 10*p + d where p is a number reachable in 1 step, and d ∈ S. For any node (k), the "shortest path" to (k), i.e. the smallest value 10*p+d for which

will just be the smallest value of p for which

i.e. the smallest value of p (ties broken by d) for which

But notice now that because p is a 1-digit number, from the previous step we stored the smallest value of p for which this holds true. So we don't need to check every possible value of p, we only need to check the values for p which were the smallest possible paths to some node on the previous step.

Which is quite a lot of justification for the algorithm, but at the end of the day, it simply means we notice that

shortest path to (1) is 1 so
   with d=1, (2) is reachable in length 11 (p=1, d=1 10p+d=11=2 mod 9)
   with d=3, (4) is reachable in length 13 (p=1, d=3 10p+d=13=4 mod 9)
shortest path to (3) is 3 so
   with d=1, (4) is reachable in length 31 (p=3, d=1 10p+d=31=4 mod 9)
   with d=3, (6) is reachable in length 33 (p=3, d=3 10p+d=33=6 mod 9)

So the shortest paths to each of the reachable nodes are

(1)->1
(3)->3
(2)->11
(4)->13
(6)->33

And all the other nodes are unreachable.

At each iteration, we can repeat this same trick, that a i-digit number is just 10*p+d where p is a (i-1)-digit number. So we only need to search over the values of p stored from the previous step, and we will be guaranteed to find the shortest path of length <=i, i.e. the smallest number equal to k mod m.

Thus each step will potentially increase the size of the reachable nodes, and if 0 is ever reachable, we have found the minimal solution to our equation. But what about if 0 is not reachable, how will we tell when to stop searching? The key is that every iteration of our algorithm is exactly the same, so if at some iteration the set of reachable nodes does not change, then we know that it will never change again no matter how long we wait. Because there are a finite number of nodes, we know that either we must eventually reach zero, or our set of nodes must reach a fixed limit, terminating our algorithm.

So to finish our example, we have

shortest path to (2) is 11 so
   with d=1, (3) is reachable in length 111 (p=11, d=1 10p+d=111=3 mod 9)
   with d=3, (5) is reachable in length 13 (p=11, d=3 10p+d=113=5 mod 9)
shortest path to (4) is 13 so
   with d=1, (5) is reachable in length 131 (p=13, d=1 10p+d=131=5 mod 9)
   with d=3, (7) is reachable in length 133 (p=13, d=3 10p+d=133=7 mod 9)
shortest path to (6) is 33 so
   with d=1, (7) is reachable in length 331 (p=11, d=1 10p+d=331=7 mod 9)
   with d=3, (0) is reachable in length 333 (p=11, d=3 10p+d=333=0 mod 9)

which means we found the shortest path to (0), which is 333.

Space complexity:

For every value 0 <= i < m, we need to store a single digit and a pointer to the previous node in the path, which will require O(m) storage overall.

Running Time:

Every node in the graph requires us to consider a transition for each digit d ∈ S. Thus the running time will be O(m*r) where r is the size of the set of acceptable digits S.

Bound on the solution:

Finally, we can use the algorithm to put a bound on the size of the solution. Since the search terminates after at most m steps, and we know it will examine solutions of at most size 10ⁱ in i steps, we know the solution must be bounded by 10^m.

Obviously this algorithm is adaptable to bases other than 10.

Answer 2

I would just recursively search for such a number. The thing is you need a nice way to stop. I my algorithm I just poorly check for overflow. You can chose something better like the depth you want to search.

public static long find(int n, int[] digits, long current) {
    if (current > 0 && current % n == 0) {
        return current;
    }
    if (current < 0) {
        return Long.MAX_VALUE;//overflow
    }
    List<Long> all = new ArrayList<>();
    for (int i : digits) {
        long nc = current * 10 + i;
        all.add(find(n, digits, nc));
    }
    long found = Long.MAX_VALUE;
    for (long i : all) {
        if (i > 0) {
            found = Math.min(found, i);
        }
    }
    return found;
}

public static void main(String... args) {
    System.out.println("aaa");
    int d[] = {1, 3};
    System.out.println(find(7, d, 0));
}

The size of the number is limited by long max value. You can use BigInteger insted of long and go as much as you want

Answer 3

Personally, I'd go about this in reverse. Take your M number, and multiply it by 1. Can you find M*1's digits among yours? If no, then go to M*2. You can stop at some arbitrarily high number. If you're using ints you can just stop to INT_MAX or whatever.

Edit : You can actually stop at INT_MAX-M.