We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Tried solving it using DP but ended up with stack overflow error..
then tried my luck with BFS queue approach... was able to solve it....
Steps:
for each N add the maxFactors of N and N-1 to the queue
then pick up every element from queue and do the same until u reach zero...
in each step update the level (or length ) for the factors found
For example
N=20
20
5 10 19
4 5 9
2 4 8 3
1 2
0 1
0
when you go with factor 5 u reach 0 first....and you can ignore
remaining elements in the queue.
20->5->4->2->1->0
publicclassDownZero{privatestaticDeque<Value>queue=newArrayDeque<>();privatestaticMap<Integer,Value>mapStore=newHashMap<>();publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intN=sc.nextInt();for(inti=0;i<N;i++){intm=sc.nextInt();queue.clear();clearVisited();queue.add(getValue(m));System.out.println(move(getValue(m)));}}publicstaticintmove(Valueb){b=queue.poll();while(b!=null){if(b.getNum()==0)return0;if(b.getNum()-1==0)returngetValue(b.getNum()).getLevel()+1;if(b.getNum()==2)returngetValue(b.getNum()).getLevel()+2;if(b.visited==true){b=queue.poll();continue;}// int m = 1 + min(b-1);intm1=0;List<Value>f=allMaxFactors(b.getNum());// System.out.println(b+"->"+f);f.add(getValue(b.getNum()-1));if(f.size()>0){b.setVisited(true);queue.addAll(f);// queue.add(getValue(b.getNum()-1));setLength(f,b);}b.setVisited(true);b=queue.poll();}return0;}publicstaticList<Value>allMaxFactors(inta){intupperlimit=(int)(Math.sqrt(a));List<Integer>factors=newArrayList<Integer>();List<Value>maxfactors=newArrayList<Value>();for(inti=2;i<=upperlimit;i+=1){if(a%i==0){factors.add(i);if((a/i)!=a&&(a/i)!=1){// factors.add(a/i);maxfactors.add(getValue(a/i));}}}Collections.sort(maxfactors);returnmaxfactors;}publicstaticvoidsetLength(List<Value>values,Valueb){for(Valuev:values){if(v.getLevel()==0||b.getLevel()+1<=v.getLevel())v.setLevel(b.getLevel()+1);}}publicstaticValuegetValue(inta){if(mapStore.containsKey(a))returnmapStore.get(a);else{Valuev=newValue(a);mapStore.put(a,v);returnmapStore.get(a);}}publicstaticvoidclearVisited(){Set<Integer>set=mapStore.keySet();for(Integeri:set){Valuev=mapStore.get(i);v.setVisited(false);v.setLevel(0);}}}classValueimplementsComparable<Value>{intnum;booleanvisited;intlevel;List<Value>factors=newArrayList<Value>();publicValue(intnum){this.num=num;}publicList<Value>getFactors(){returnfactors;}publicvoidsetFactors(List<Value>factors){this.factors=factors;}publicintgetNum(){returnnum;}publicvoidsetNum(intnum){this.num=num;}publicbooleanisVisited(){returnvisited;}publicvoidsetVisited(booleanvisited){this.visited=visited;}publicintgetLevel(){returnlevel;}publicvoidsetLevel(intlevel){this.level=level;}@OverridepublicStringtoString(){return" [num="+num+", level="+level+"]";}@OverridepublicintcompareTo(Valueo){if(this.getNum()>(o).getNum())return1;elseif(this.getNum()<(o).getNum())return-1;elsereturn0;}}
Down to Zero II
You are viewing a single comment's thread. Return to all comments →
Tried solving it using DP but ended up with stack overflow error.. then tried my luck with BFS queue approach... was able to solve it.... Steps: for each N add the maxFactors of N and N-1 to the queue then pick up every element from queue and do the same until u reach zero... in each step update the level (or length ) for the factors found For example N=20 20 5 10 19 4 5 9 2 4 8 3 1 2
0 1 0
when you go with factor 5 u reach 0 first....and you can ignore remaining elements in the queue.
20->5->4->2->1->0