Yet another BFS solution in c++

#1 
string Solution::multiple(int N) {
    if(N==1) return "1";
    vector<int> p(N,-1);//parent state
    vector<int> s(N,-1);//step from parent to current
    //BFS
    int steps[2] = {0,1};
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        if(curr==0) break;
        for(int step: steps){
            int next = (curr*10+step)%N;
            if(p[next]==-1){
                p[next]=curr;
                s[next]=step;
                q.push(next);
            }
        }
    }
    //build reversed string
    string number;
    for(int it=0; it!=1; it=p[it])
        number.push_back('0'+s[it]);
    number.push_back('1');
    //return the reverse if it
    return string(number.rbegin(), number.rend());
}
#2

Nice! I like the steps abstraction. Instead of while(!q.empty()) (which will never happen) and if(curr==0) break to exit the while loop, you could have while (q.front() != 0).

And here’s an alternate way to build the answer in order:

deque<char> number;
for (int state = 0; state != 1; state = parentStates[state]) {
    number.push_front('0' + stateDigits[state]);
}
number.push_front('1');
return string(number.begin(), number.end());
#3

Could you please explain your solution?

#4

Let’s understand the solution from very starting ,
Take a simple problem suppose we need to find mod/remainder of a large no. greater than long long. What we do
We have the big number as string t , int r=0;
for ( int i = 0; i < t.length(); i++)
{
r = r * 10 + (t[i] - '0' );
r %= N;
}
So take for example string t1=“111” and string t2=“111111” N=3
Suppose we need to append more 1’s and 0’s to both strings to obtain another multiple of 3
then we will take t1 to obtain the next smallest multiple not t2 because it is larger and both gives mod 0 when divided by 3.
Similarly in @ValkA 's solution whenever we have already reached state where p[i]!=-1
we do not update the string because this time we will have larger string or number than previous.
Alternatively we could have directly stored string instead of storing parent and state , so that we need not form the number , but for that we need to implement an extra mod function as shown earlier.
Hope it Helps!

#5

I use your concept with some modification. Can you help me with TLE :

string Solution::multiple(int A) {
vector<pair<string,int> > qu;
if(A==1) return “1”;
if(A==0) return “0”;
qu.push_back(make_pair(“1”,1));
unordered_set rem;
rem.insert(1);
while(!qu.empty())
{
int n=qu.size();
for(int i=0;i<n;i++)
{
pair<string,int> root=qu.front();
qu.erase(qu.begin());

        string s=root.first+"0";
        int I=(root.second*10)%A;
        if(I==0) return s;
        if(rem.find(I)==rem.end()){
        qu.push_back(make_pair(s,I));
        rem.insert(I);}
        
        s=root.first+"1";
        I=(root.second*10+1)%A;
        if(I==0) return s;
        if(rem.find(I)==rem.end()){
        qu.push_back(make_pair(s,I));
        rem.insert(I);}
    }
}

}