Simple Java Solution using tree and queue


#1

public class Solution {
public class Node {
int val;
int step;
Node prev;
Node(Node p, int v,int s) {
prev=p;
step=s;
val=v;
}
}
public String multiple(int n) {
if(n==0 ||n==1) return Integer.toString(n);
Queue q = new LinkedList<>();
boolean visit[] = new boolean[n+1];
visit[1%n]=true;
// Node res = new Node()
q.offer(new Node(null,1%n,1));
Node temp=null;
while(!q.isEmpty()){
temp= q.poll();
int val = temp.val*10;
if(val==0){
break;
}
if(!visit[val%n]){
q.offer(new Node(temp,val%n,0));
visit[val%n]=true;
}
if(!visit[(val+1)%n]){
q.offer(new Node(temp,(val+1)%n,1));
visit[(val+1)%n]=true;
}
}
StringBuilder s = new StringBuilder();
while(temp!=null){
s.append(temp.step);
temp=temp.prev;
}
return s.reverse().toString();
}
}


#2

What is reason for using StringBuilder?


#3

String builder is used to maintain the list of no from bottom to up.You can use string also.
suppose give n no is 7.
1
/
3 4
/ . /
2 3 5
/
6 7
as soon as 7 encounters means multiple of 7 found then move from bottom 7 to top 1. and store the intermediate result to string