PWC 049 › Smallest multiple containing only 1 and 0

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week is as follows:

Write a script to accept a positive number as command line argument and print the smallest multiple of the given number consists of digits 0 and 1.

Brute Force

It’s easy enough to brute force this problem, by checking every multiple in order:

$_ += $_[0] while /[^10]/;

$_ now contains the answer. Unfortunately, some numbers—particularly multiples of 9—require extremely large multiples. For example, 99 × 1122334455667789 = 111111111111111111 takes several minutes to discover via this method.

We can do better, though.

Breadth-First Search (BFS)

Quite often, when a search space gets too large, it helps to look at the problem from the other direction. In this case, instead of looking at every multiple and seeing if it only contains 1s and 0s, we can look at every number containing 1s and 0s and see if it is a multiple. This turns out to be substantially faster for larger multiples (and not much slower on smaller ones):

Perl

sub mult_bfs {
    my $n = shift;

    my $cur;
    for (my (@r) = $cur = 1; $cur % $n; $cur = shift @r) {
        push @r, $cur . 0, $cur . 1;
    }
    $cur;
}

mult_bfs(45) runs about 1,500,000% faster than the brute force equivalent. It prints the results for 1..100 in about a quarter of a second on my system.

Another way to write this would be to iterate normally, and then convert the number to binary with sprintf "%b". That turns out to be around 50% faster:

 sub mult_sprintf {
     my $n = shift;

     for (my $i = 1; ; $i++) {
         my $cur = sprintf '%b', $i;
         return $cur if 0 == $cur % $n;
     }
 }

Raku

The sprintf (or in this case base or fmt) solution can be done very concisely in Raku:

sub mult_base( Int \N ) { (1..∞).map( *.base(2) ).first( * %% N ) }

The lazy sequence (1..∞) is mapped to its binary equivalent, and then the first element where that (base-10) string of 1s and 0s is divisible by N is returned.

Printing the results from 1..100 takes longer in Raku (about 6 seconds), but this is possibly hours faster than the brute force approach would have been.