string Solution::multiple(int n) {
if(n==1) return "1";
vector<long long> dp(n,0);
dp[1] = 1;
queue<int> q;
q.push(1);
while(!q.empty()){
int r = q.front(); q.pop();
if(r==0){
string res;
while(dp[r]){
res += '0' + dp[r]%2;
dp[r] /= 2;
}
reverse(res.begin(),res.end());
return res;
}
for(auto x : {0,1}){
int new_r = (10*r + x)%n;
if(dp[new_r]==0){
q.push(new_r);
dp[new_r] = dp[r]*2 + x;
}
}
}
}
Youtube video link: https://www.youtube.com/watch?v=sdTubUR99OA