```
if(A==1) return "1";
queue<string> q;
q.push("1");
while(!q.empty()){
int n=q.size();
for(int i=0;i<n;i++){
string s=q.front();
q.pop();
if(stol(s)%A==0){
return s;
}
q.push(s+'0');
q.push(s+'1');
}
}
return "0";.
```

# Used tree, but got Memory Limit Exceeded, although the solution uses O(n) memory (easiest solution)

Memory grows exponentially and we have a complete binary tree structure it means if ans is of 20 digit we would store 2 pow 20 strings in queue…moreover max size of s is not 18 so long long may not work …do division through loop…