Check if it is possible to reach a number by making jumps of two given length | JavaScript implementation of the approach ; Function to perform BFS traversal to find minimum number of step needed to reach x from K ; Calculate GCD of d1 and d2 ; If position is not reachable return - 1 ; Queue for BFS ; Hash Table for marking visited positions ; we need 0 steps to reach K ; Mark starting position as visited ; stp is the number of steps to reach position s ; if position not visited add to queue and mark visited ; Driver Code
function __gcd ( a , b ) { if ( b == 0 ) return a ; return __gcd ( b , a % b ) ; } function minStepsNeeded ( k , d1 , d2 , x ) { let gcd = __gcd ( d1 , d2 ) ; if ( ( k - x ) % gcd != 0 ) return - 1 ; let q = [ ] ; let visited = new Set ( ) ; q . push ( [ k , 0 ] ) ; visited . add ( k ) ; while ( q . length != 0 ) { let s = q [ 0 ] [ 0 ] ; let stp = q [ 0 ] [ 1 ] ; if ( s == x ) return stp ; q . shift ( ) ; if ( ! visited . has ( s + d1 ) ) { q . push ( [ s + d1 , stp + 1 ] ) ; visited . add ( s + d1 ) ; } if ( ! visited . has ( s + d2 ) ) { q . push ( [ s + d2 , stp + 1 ] ) ; visited . add ( s + d2 ) ; } if ( ! visited . has ( s - d1 ) ) { q . push ( [ s - d1 , stp + 1 ] ) ; visited . add ( s - d1 ) ; } if ( ! visited . has ( s - d2 ) ) { q . push ( [ s - d2 , stp + 1 ] ) ; visited . add ( s - d2 ) ; } } return Number . MIN_VALUE ; } let k = 10 , d1 = 4 , d2 = 6 , x = 8 ; document . write ( minStepsNeeded ( k , d1 , d2 , x ) ) ;