Smallest Multiple With 0 and 1

• Time : $O(A)$
• Space : $O(A)$

string Solution::multiple(int A) {
    queue<int> q;
    q.push(1%A);
    vector<int> vis(A + 1);
    vis[1%A] = 1;
    vector<pair<int,char>> par(A+1,{-1,'1'});
    while(q.size()) {
        auto now = q.front(); q.pop();
        if(!now) {
            string res = "";
            res.push_back(par[0].second);
            int p = par[0].first;
            while(p != -1) {
                res.push_back(par[p].second);
                p = par[p].first;
            }
            reverse(begin(res), end(res));
            return res;
        }
        
        int m10 = (now*10)%A, m11= ((now*10)%A+1)%A;
        if(!vis[m10]) {
            q.push(m10);
            vis[m10] = true;
            par[m10] = {now, '0'};
        }
        if(!vis[m11]) {
            q.push(m11);
            vis[m11] = true;
            par[m11] = {now, '1'};
        }
    }
    return "";
}