Smallest Multiple With 0 and 1

You are given an integer N. You have to find smallest multiple of N which consists of digits 0 and 1 only. Since this multiple could be large, return it in form of a string.

Note:

For example,

For N = 55, 110 is smallest multiple consisting of digits 0 and 1.
For N = 2, 10 is the answer.

Solution:

import java.math.BigInteger;

public class Solution {
    private boolean isMultiple(BigInteger n, int A) {
        BigInteger divider = new BigInteger(String.valueOf(A));
        if (n.mod(divider).equals(BigInteger.ZERO)) {
            return true;
        }
        return false;
    }
    
    public String multiple(int A) {
        Deque<StringBuilder> queue = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        sb.append("1");
        queue.offer(sb);
        while (!queue.isEmpty()) {
            StringBuilder curr = queue.poll();
            BigInteger n = new BigInteger(curr.toString());
            if (isMultiple(n, A)) {
                return curr.toString();
            }
            StringBuilder addOne = new StringBuilder(curr.toString());
            curr.append("0");
            queue.offer(curr);
            addOne.append("1");
            queue.offer(addOne);
        }
        return "";
    }
}

Space optimized:

public class Solution {
    public String multiple(int A) {
        if (A == 1) return "1";
        Deque<Integer> queue = new ArrayDeque<>();

        int[] parent = new int[A];
        int[] state = new int[A];
        int[] steps = new int[]{0, 1};
        for (int i = 0; i < A; i ++) {
            parent[i] = -1;
            state[i] = -1;
        }
        queue.offer(1);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == 0) {
                break;
            }
            for(int step: steps) {
                int next = (curr * 10 + step) % A;
                if(parent[next] == -1){
                    parent[next] = curr;
                    state[next] = step;
                    queue.offer(next);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        int s = 0;
        while (s != 1) {
            sb.append(String.valueOf(state[s]));
            s = parent[s];
        }
        sb.append("1");
        return sb.reverse().toString();
    }
}