Still getting TLE. Tell me where I am doing wrong


#1

string Solution::multiple(int A) {

queue<int> q;
vector<bool> visited(A);
vector<int> parent(A);
vector<bool> digit(A);
// unordered_map<int,pair<int,bool>> res;
int rem = 1%A;
visited[rem] = 1;
parent[rem] = -1;
digit[rem] = 1;
// res[rem] = make_pair(-1,1);

q.push(rem);

while(!q.empty())
{
    int p = q.front();
    q.pop();
    // cout<<mod1<<" "<<mod2<<" "<<p.second<<endl;
    if (p == 0) break;
    int mod1 = (p*10+1)%A;
    int mod2 = (p*10)%A;

    if(visited[mod1]==0)
    {
        visited[mod1] = 1;
        parent[mod1] = p;
        digit[mod1] = 1;
        q.push(mod1);
    }
    
    if(visited[mod2]==0)
    {
        visited[mod2] = 1;
        parent[mod2] = p;
        digit[mod2] = 0;
        q.push(mod2);
    }
}

string ans = "";

int i = 0;
while(i!=-1)
{
    if(digit[i]) ans.push_back('1');
    else ans.push_back('0');
    i = parent[i];
}

reverse(ans.begin(),ans.end());

return ans;

}


#2

Hey,
Just in case you haven’t figured it out till now, you are first pushing the bigger number(1 appended) in your queue and then the smaller (0 appended) which might be causing the TLE, try putting your mod2 if condition above mod1 condition.