n_multiple_Min_N_Zeros_Ones.rb

NUM = 2000
pow, val = [], []

2.upto NUM-1 do |num|
    0.upto(NUM-1) {|i| pow[i] = 0 }
    count, ten, x = 0, 1, 1

    while (x < NUM) do
        val[x] = ten
        0.upto NUM-1 do |j|
            if (pow[j] != 0 && pow[(j + ten) % num] == 0 && pow[j] != x)
                    pow[(j+ten) % num] = x
            end
        end
        if (pow[ten] == 0)
            pow[ten] = x
        end
        ten = (10 * ten) % num
        if (pow[0] != 0)
            break;
        end
        x += 1
    end

    x = num;
    print "%d\tdivides\t" % [x]
    if (pow[0] != 0) then
        while (x != 0) do
            count -= 1
            while (count > (pow[x % num] - 1)) do
                print "0"
                count -= 1
            end

            count = pow[x % num] - 1
            print "1"
            x = (num + x - val[pow[x % num]]) % num;
        end
        while (count > 0) do
            print "0"
            count -= 1
        end
    else
        puts "Can't do it!"
    end
    puts
end