Smallest Multiple of given number With digits only 0 and 1

Question

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.

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.

I saw several related problems, but I could not find the problem with my code. Here is my code giving TLE on some cases even after using map instead of set.

#define ll long long
int getMod(string s, int A)
{
    int res=0;
    for(int i=0;i<s.length();i++)
    {
        res=res*10+(s[i]-'0');
        res%=A;
    }
    return res;
}
string Solution::multiple(int A) {
    if(A<=1)
    return to_string(A);

    queue<string>q;
    q.push("1");
    set<int>st;
    string s="1";

    while(!q.empty())
    {
        s=q.front();
        q.pop();
        int mod=getMod(s,A);
        if(mod==0)
        {
            return s;
        }
        else if(st.find(mod)==st.end())
        {
            st.insert(mod);
            q.push(s+"0");
            q.push(s+"1");
        }
    }

}

Answer 1

As mentioned in the "math" reference, the result is related to the congruence of the power of 10 modulo A.

If

n = sum_i a[i] 10^i

then

n modulo A = sum_i a[i] b[i]

Where the a[i] are equal to 0 or 1, and the b[i] = (10^i) modulo A

Then the problem is to find the minimum a[i] sequence, such that the sum is equal to 0 modulo A.

From a graph a point of view, we have to find the shortest path to zero modulo A.

A BFS is generally well adapted to find such a path. The issue is the possible exponential increase of the number of nodes to visit. Here, were are sure to get a number of nodes less than A, by rejecting the nodes, the sum of which (modulo A) has already been obtained (see vector used in the program). Note that this rejection is needed in order to get the minimum number at the end.

Here is a program in C++. The solution being quite simple, it should be easy to understand even by those no familiar with C++.

#include <iostream>
#include <string>
#include <vector>

struct node {
    int sum = 0;
    std::string s;
};

std::string multiple (int A) {
    std::vector<std::vector<node>> nodes (2);
    std::vector<bool> used (A, false);
    int range = 0;
    int ten = 10 % A;
    int pow_ten = 1;

    if (A == 0) return "0";
    if (A == 1) return "1";

    nodes[range].push_back (node{0, "0"});
    nodes[range].push_back (node{1, "1"});
    used[1] = true;

    while (1) {
        int range_new = (range + 1) % 2;
        nodes[range_new].resize(0);
        pow_ten = (pow_ten * ten) % A;

        for (node &x: nodes[range]) {
            node y = x;
            y.s = "0" + y.s;
            nodes[range_new].push_back(y);
            y = x;
            y.sum = (y.sum + pow_ten) % A;
            if (used[y.sum]) continue;
            used[y.sum] = true;
            y.s = "1" + y.s;
            if (y.sum == 0) return y.s;
            nodes[range_new].push_back(y);
        }
        range = range_new;
    }
}

int main() {
    std::cout << "input number: ";
    int n;
    std::cin >> n;
    std::cout << "Result = " << multiple(n) << "\n";
    return 0;
}

EDIT

The above program is using a kind of memoization in order to speed up the process but for large inputs memory becomes too large. As indicated in a comment for example, it cannot handle the case N = 60000007.

I improved the speed and the range a little bit with the following modifications:

• A function (reduction) was created to simplify the search when the input number is divisible by 2 or 5
• For the memorization of the nodes (nodes array), only one array is used now instead of two
• A kind of meet-in-the middle procedure is used: in a first step, a function mem_gen memorizes all relevant 01 sequences up to N_DIGIT_MEM (=20) digits. Then the main procedure multiple2 generates valid 01 sequences "after the 20 first digits" and then in the memory looks for a "complementary sequence" such that the concatenation of both is a valid sequence

With this new program the case N = 60000007 provides the good result (100101000001001010011110111, 27 digits) in about 600ms on my PC.

EDIT 2

Instead of limiting the number of digits for the memorization in the first step, I now use a threshold on the size of the memory, as this size does not depent only on the number of digits but also of the input number. Note that the optimal value of this threshold would depend of the input number. Here, I selected a thresholf of 50k as a compromise. With a threshold of 20k, for 60000007, I obtain the good result in 36 ms. Besides, with a threshold of 100k, the worst case 99999999 is solved in 5s.

I made different tests with values less than 10^9. In about all tested cases, the result is provided in less that 1s. However, I met a corner case N=99999999, for which the result consists in 72 consecutive "1". In this particular case, the program takes about 6.7s. For 60000007, the good result is obtained in 69ms.

Here is the new program:

    #include <iostream>
    #include <string>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <chrono>
    #include <cmath>
    #include <algorithm>

    std::string reverse (std::string s) {
        std::string res {s.rbegin(), s.rend()};
        return res;
    }

    struct node {
        int sum = 0;
        std::string s;
        node (int sum_ = 0, std::string s_ = ""): sum(sum_), s(s_) {};
    };

//  This function simplifies the search when the input number is divisible by 2 or 5
    node reduction (int &X, long long &pow_ten) {
        node init {0, ""};
        while (1) {
            int digit = X % 10;
            if (digit == 1 || digit == 3 || digit == 7 || digit == 9) break;
            switch (digit) {
                case(0):
                    X /= 10;
                    break;
                case(2):
                case(4):
                case(6):
                case(8):
                    X = (5*X)/10;
                    break;
                case(5):
                    X = (2*X)/10;
                    break;
            }
            init.s.push_back('0');
            pow_ten = (pow_ten * 10) % X;
        }       
        return init;
    }

const int N_DIGIT_MEM = 30;     // 20
const int threshold_size_mem = 50000;

//  This function memorizes all relevant 01 sequences up to N_DIGIT_MEM digits
bool gene_mem (int X, long long &pow_ten, int index_max, std::map<int, std::string> &mem, node &result) {

    std::vector<node> nodes;
    std::vector<bool> used (X, false);
    bool start = true;

    for (int index = 0; index < index_max; ++index){
        if (start) {
                node x = {int(pow_ten), "1"};
                nodes.push_back (x);
        } else {
            for (node &x: nodes) {
                x.s.push_back('0');
            }
            int n = nodes.size();

            for (int i = 0; i < n; ++i) {
                node y = nodes[i];
                y.sum = (y.sum + pow_ten) % X;
                y.s.back() = '1';
                if (used[y.sum]) continue;
                used[y.sum] = true;
                if (y.sum == 0) {
                    result = y;
                    return true;
                }
                nodes.push_back(y);
            }   
        }
        pow_ten = (10 * pow_ten) % X;
        start = false;
        int n_mem = nodes.size();
        if (n_mem > threshold_size_mem) {
            break;
        }
    }
    for (auto &x: nodes) {
        mem[x.sum] = x.s;
    }
    //std::cout << "size mem = " << mem.size() << "\n";
    return false;
}
//  This function generates valid 01 sequences "after the 20 first digits" and then in the memory 
//  looks for a "complementary sequence" such that the concatenation of both is a valid sequence
    std::string multiple2 (int A) {
        std::vector<node> nodes;
        std::map<int, std::string> mem;
        int ten = 10 % A;
        long long pow_ten = 1;
        int digit;

        if (A == 0) return "0";
        int X = A;
        node init = reduction (X, pow_ten);

        if (X != A) ten = ten % X;

        if (X == 1) {
            init.s.push_back('1');
            return reverse(init.s);
        }
        std::vector<bool> used (X, false);
        node result;
        int index_max = N_DIGIT_MEM;
        if (gene_mem (X, pow_ten, index_max, mem, result)) {
            return reverse(init.s + result.s);
        }   

        node init2 {0, ""};
        nodes.push_back(init2);

        while (1) {
            for (node &x: nodes) {
                x.s.push_back('0');
            }
            int n = nodes.size();
            for (int i = 0; i < n; ++i) {
                node y = nodes[i];
                y.sum = (y.sum + pow_ten) % X;
                if (used[y.sum]) continue;
                used[y.sum] = true;
                y.s.back() = '1';
                if (y.sum != 0) {
                    int target = X - y.sum;
                    auto search = mem.find(target);
                    if (search != mem.end()) {
                        //std::cout << "mem size 2nd step = " << nodes.size() << "\n";
                        return reverse(init.s + search->second + y.s);
                    }
                }
                nodes.push_back(y);
            }
            pow_ten = (pow_ten * ten) % X;
        }
    }

    int main() {
        std::cout << "input number: ";
        int n;
        std::cin >> n;
        std::string res;

        auto t1 = std::chrono::high_resolution_clock::now();
        res = multiple2(n),
        std::cout << "Result = " << res << "  ndigit = " << res.size() << std::endl;
        auto t2 = std::chrono::high_resolution_clock::now();
        auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
        std::cout << "time = " << duration2/1000 << " ms" << std::endl;

        return 0;
    }

Answer 2

Here is an implementation in Raku.

my $n = 55;
(1 .. Inf).map( *.base(2) ).first( * %% $n );

(1 .. Inf) is a lazy list from one to infinity. The "whatever star" * establishes a closure and stands for the current element in the map.

base is a method of Rakus Num type which returns a string representation of a given number in the wanted base, here a binary string.

first returns the current element when the "whatever star" closure holds true for it.

The %% is the divisible by operator, it implicitly casts its left side to Int.

Oh, and to top it off. It's easy to parallelize this, so your code can use multiple cpu cores:

 (1 .. Inf).race( :batch(1000), :degree(4) ).map( *.base(2) ).first( * %% $n );

Answer 3

For people more familiar with Python, here is a converted version of @Damien's code. Damien's important insight is to strongly reduce the search tree, taking advantage of the fact that each partial sum only needs to be investigated once, namely the first time it is encountered.

The problem is also described at Mathpuzzle, but there they mostly fix on the necessary existence of a solution. There's also code mentioned at the online encyclopedia of integer sequences. The sage version seems to be somewhat similar.

I made a few changes:

• Starting with an empty list helps to correctly solve A=1 while simplifying the code. The multiplication by 10 is moved to the end of the loop. Doing the same for 0 seems to be hard, as log10(0) is minus infinity.
• Instead of alternating between nodes[range] and nodes[new_range], two different lists are used.
• As Python supports integers of arbitrary precision, the partial results could be stored as decimal or binary numbers instead of as strings. This is not yet done in the code below.

from collections import namedtuple

node = namedtuple('node', 'sum str')

def find_multiple_ones_zeros(A):
    nodes = [node(0, "")]
    used = set()
    pow_ten = 1
    while True:
        new_nodes = []
        for x in nodes:
            y = node(x.sum, "0" + x.str)
            new_nodes.append(y)
            next_sum = (x.sum + pow_ten) % A
            y = node((x.sum + pow_ten) % A, x.str)
            if next_sum in used:
                continue
            used.add(next_sum)
            y = node(next_sum, "1" + x.str)
            if next_sum == 0:
                return y.str
            new_nodes.append(y)
        pow_ten = (pow_ten * 10) % A
        nodes = new_nodes