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

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 );