Minimum step to reach one | C ++ 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 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 to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct data { int val ; int steps ; data ( int val , int steps ) : val ( val ) , steps ( steps ) { } } ; int minStepToReachOne ( int N ) { queue < data > q ; q . push ( data ( N , 0 ) ) ; set < int > st ; while ( ! q . empty ( ) ) { data t = q . front ( ) ; q . pop ( ) ; if ( t . val == 1 ) return t . steps ; if ( st . find ( t . val - 1 ) == st . end ( ) ) { q . push ( data ( t . val - 1 , t . steps + 1 ) ) ; st . insert ( t . val - 1 ) ; } for ( int i = 2 ; i * i <= t . val ; i ++ ) { if ( t . val % i == 0 && st . find ( t . val / i ) == st . end ( ) ) { q . push ( data ( t . val / i , t . steps + 1 ) ) ; st . insert ( t . val / i ) ; } } } } int main ( ) { int N = 17 ; cout << minStepToReachOne ( N ) << endl ; }