Java Solution(Working) -Was StackOverFlow on using Set in place of array to maintain check


#1

public String multiple(int A) {

    if(A == 1) return "1";
    
    Queue<Pair> queue = new LinkedList();
    
    queue.add(new Pair(1, null, true));
    
    boolean[] checked =new boolean[A];
    
    Pair result = null;
    
 //   long count  = 0;
    
    while(!queue.isEmpty()){
        
   //     count++;
        Pair curr = queue.poll();
    
        if(curr.one == 0){ result = curr; break;}
        int zeroMod = (curr.one*10)%A;
        int oneMod = (curr.one*10 + 1)%A;
    
        if(!checked[zeroMod]){    
        queue.add(new Pair(zeroMod, curr,false));
        checked[zeroMod] = true;
        }
        if(!checked[oneMod]){
        queue.add(new Pair(oneMod, curr, true));
        checked[oneMod] = true;
        }
  //      System.out.println(count);
    }
    StringBuilder resultString = new StringBuilder();
    while(result != null){
        String s = result.isOne?"1":"0";
        resultString.append(s);
        result = result.parent;
    }
    
    
    return resultString.reverse().toString();
            
}

 class Pair{
     
    Pair parent;
    int one;
    boolean isOne;
    
    public Pair(int one , Pair parent, boolean isOne){
        this.one = one;
        this.parent = parent;
        this.isOne  = isOne;
    }
    
}