public class Solution {
public class struct{
int val;
int mod_val;
struct link;
public struct (int val,int x, struct y){
this.val=val;
this.mod_val=x;
this.link = y;
}
public String to_string(){
StringBuilder rsb = new StringBuilder();
StringBuilder sb = new StringBuilder();
struct curr = link;
rsb.append(this.val);
while(curr!=null){
rsb.append(curr.val);
curr = curr.link;
}
for(int i=rsb.length()-1; i>=0; i--){
sb.append(rsb.charAt(i));
}
return sb.toString();
}
}
public String multiple(int A) {
if(A==0) return "0"; //checking for 0
Queue <struct> q = new LinkedList<struct>();
q.add(new struct(1,1%A,null));
if(1%A == 0) return "1"; //checkcing for 1
while(!q.isEmpty()){
struct temp = q.poll();
struct left_child = new struct(0,(temp.mod_val*10)%A,temp);
q.add(left_child); // left child
if(left_child.mod_val==0){
return left_child.to_string();
}
struct right_child = new struct(1,(temp.mod_val*10+1)%A,temp);
q.add(right_child);
if(right_child.mod_val==0){
return right_child.to_string();
}
}
return "";
}
}