Solution inspired by Errichto


#1
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