How can I remove my TLE? My solution to above problem is as follows.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
bool visited[20005];
queue < pair<string, ll> > q;
pair<string, ll> p;
string ans;
void bfs(int n)
{
// cout << “hi” << endl;
memset(visited, false, sizeof(visited));
string s1, s2, s3;
s1 = s1 + ‘1’;
if (n == 1) {
ans = s1;
return;
}
ll temp, val, rem;
p = make_pair(s1, 1);
q.push(p);
while (!q.empty()) {
p = q.front();
q.pop();
s1 = p.first;
val = p.second;
if (val == 0) {
ans = s1;
return;
}
// if (visited[val] == false) {
temp = val * 10 + 1;
rem = temp % n;
s2 = s1 + '1';
p = make_pair(s2, rem);
q.push(p);
// visited[rem] = true;
temp = val * 10 + 0;
rem = temp % n;
s3 = s1 + '0';
p = make_pair(s3, rem);
q.push(p);
// visited[rem] = true;
// }
}
}
int main()
{
int k, n;
scanf("%d", &k);
while (k--) {
while (!q.empty()) {
q.pop();
}
ans.clear();
scanf("%d", &n);
bfs(n);
for (int i = 0; i < ans.size(); i++) {
printf("%c", ans[i]);
}
printf("\n");
}
return 0;
}