 # 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 = {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

#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);}
}
}
``````

}