Smallest Multiple Made of 0s and 1s

Given a positive integer n, find the smallest positive multiple of n whose decimal digits are only 0s and 1s. The result can be very long, so return it as a string.

Example

Text

n = 2     ->  "10"
n = 7     ->  "1001"         (7 × 143)
n = 18    ->  "1111111110"   (18 × 61728395)

Brute force: try multiples of n

Check n, 2n, 3n, ... until one has only 0 and 1 digits.

Java

public class Main {
    static boolean onlyZerosAndOnes(long x) {
        while (x > 0) {
            if (x % 10 > 1) {
                return false;
            }
            x /= 10;
        }
        return true;
    }

    static String smallestMultiple(long n) {
        for (long k = 1; ; k++) {
            long m = k * n;
            if (onlyZerosAndOnes(m)) {
                return Long.toString(m);
            }
        }
    }

    public static void main(String[] args) {
        for (long n : new long[]{2, 7, 18}) {
            System.out.println(n + " -> " + smallestMultiple(n));
        }
    }
}

Output

2 -> 10
7 -> 1001
18 -> 1111111110

Time: unbounded in practice: for n = 18 it already tries 61,728,395 multiples. Space: O(1).

For n = 99, the answer is 111111111111111111 (18 ones), about 1.1 × 10¹⁶, so this loop would need about 10¹⁴ tries. For some n (such as 9999, whose answer has 36 digits), the answer doesn't even fit in a long, so k * n would overflow and wrap around silently.

Optimal: BFS over remainders

Build candidates from the left, digit by digit: start with "1", and from any candidate s, the next candidates are s + "0" and s + "1". Breadth-first search visits them from shortest to longest, and among equal lengths, 0 before 1, which is numerical order. So the first multiple of n found is the smallest.

The numbers themselves grow without bound (a Java long holds at most 19 digits), but only their remainder modulo n matters for divisibility. Appending a digit d changes the remainder r to (10r + d) % n. There are only n possible remainders, and two candidates with the same remainder behave identically from then on, so only the first (smallest) one needs to be kept. The search visits at most n states.

To rebuild the answer, each remainder remembers the remainder it came from and the digit that was appended. StringBuilder collects the digits, and reverse puts them in order. The product r * 10 + d is computed as a long so it cannot overflow int for large n.

Java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
    static String smallestMultiple(int n) {
        int[] prev = new int[n];      // prev[r] = remainder this one came from, -1 for the start
        char[] digit = new char[n];   // digit[r] = digit appended to reach r
        boolean[] seen = new boolean[n];
        int start = 1 % n;
        seen[start] = true;
        prev[start] = -1;
        digit[start] = '1';
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int r = queue.poll();
            if (r == 0) {
                break;
            }
            for (int d = 0; d <= 1; d++) {
                int next = (int) (((long) r * 10 + d) % n); // long avoids int overflow for large n
                if (!seen[next]) {
                    seen[next] = true;
                    prev[next] = r;
                    digit[next] = (char) ('0' + d);
                    queue.add(next);
                }
            }
        }
        StringBuilder digits = new StringBuilder();
        for (int r = 0; r != -1; r = prev[r]) {
            digits.append(digit[r]);
        }
        return digits.reverse().toString();
    }

    public static void main(String[] args) {
        for (int n : new int[]{1, 2, 7, 18, 99, 9999}) {
            System.out.println(n + " -> " + smallestMultiple(n));
        }
    }
}

Output

1 -> 1
2 -> 10
7 -> 1001
18 -> 1111111110
99 -> 111111111111111111
9999 -> 111111111111111111111111111111111111

Time: O(n): at most n remainders, each expanded once. Space: O(n).

A remainder of 0 is always reached: among the n + 1 numbers 1, 11, 111, ..., two have the same remainder, and their difference (11...100...0) is a multiple of n made of 0s and 1s.

Edge cases

n = 1: the start remainder 1 % 1 is already 0, and the answer is "1".
Powers of ten: "1" followed by zeros, found by always appending 0.