Minimum step to reach one | Java program to get minimum step to reach 1 under given constraints ; structure represent one node in queue ; method returns minimum step to reach one ; set is used to visit numbers so that they won 't be pushed in queue again ; loop until we reach to 1 ; if current data value is 1 , return its steps from N ; check curr - 1 , only if it not visited yet ; loop from 2 to Math . sqrt ( value ) for its divisors ; check divisor , only if it is not visited yet if i is divisor of val , then val / i will be its bigger divisor ; Driver code
import java . util . * ; class GFG { static class data { int val ; int steps ; public data ( int val , int steps ) { this . val = val ; this . steps = steps ; } } ; static int minStepToReachOne ( int N ) { Queue < data > q = new LinkedList < > ( ) ; q . add ( new data ( N , 0 ) ) ; HashSet < Integer > st = new HashSet < Integer > ( ) ; while ( ! q . isEmpty ( ) ) { data t = q . peek ( ) ; q . remove ( ) ; if ( t . val == 1 ) return t . steps ; if ( ! st . contains ( t . val - 1 ) ) { q . add ( new data ( t . val - 1 , t . steps + 1 ) ) ; st . add ( t . val - 1 ) ; } for ( int i = 2 ; i * i <= t . val ; i ++ ) { if ( t . val % i == 0 && ! st . contains ( t . val / i ) ) { q . add ( new data ( t . val / i , t . steps + 1 ) ) ; st . add ( t . val / i ) ; } } } return - 1 ; } public static void main ( String [ ] args ) { int N = 17 ; System . out . print ( minStepToReachOne ( N ) + "NEW_LINE"); } }