> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/smallest-multiple-with-0-and-1.md).

# 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**:

* Returned string should not contain leading zeroes.

For example,

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

```java
public class Solution {

    public static class Node {
        String value;
        int modN = -1;

        public Node(String x, int y) {
            value = x;
            modN = y;
        }
    }

    public String multiple(int N) {

        Deque<Node> queue = new LinkedList<>();
        queue.addLast(new Node("1", 1 % N));
        boolean[] visited = new boolean[N];
        visited[1 % N] = true;
        while (!queue.isEmpty()) {
            Node node = queue.pollFirst();
            // If we reach a multiple of N
            if (node.modN == 0)
                return node.value;
            // option 1 -> put 0 in previous answer's end
            int s1 = (node.modN * 10 + 0) % N;
            // option 2 -> put 1 in previous answer's end
            int s2 = (node.modN * 10 + 1) % N;
            if (!visited[s1]) {
                queue.addLast(new Node(node.value + "0", s1));
                visited[s1] = true;
            }
            if (!visited[s2]) {
                queue.addLast(new Node(node.value + "1", s2));
                visited[s2] = true;
            }
        }
        return "";
    }
}
```