Check if it is possible to reach a number by making jumps of two given length | Python3 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
from math import gcd as __gcd NEW_LINE from collections import deque as queue NEW_LINE def minStepsNeeded ( k , d1 , d2 , x ) : NEW_LINE INDENT gcd = __gcd ( d1 , d2 ) NEW_LINE if ( ( k - x ) % gcd != 0 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT q = queue ( ) NEW_LINE visited = dict ( ) NEW_LINE q . appendleft ( [ k , 0 ] ) NEW_LINE visited [ k ] = 1 NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT sr = q . pop ( ) NEW_LINE s , stp = sr [ 0 ] , sr [ 1 ] NEW_LINE if ( s == x ) : NEW_LINE INDENT return stp NEW_LINE DEDENT if ( s + d1 not in visited ) : NEW_LINE INDENT q . appendleft ( [ ( s + d1 ) , stp + 1 ] ) NEW_LINE visited [ ( s + d1 ) ] = 1 NEW_LINE DEDENT if ( s + d2 not in visited ) : NEW_LINE INDENT q . appendleft ( [ ( s + d2 ) , stp + 1 ] ) NEW_LINE visited [ ( s + d2 ) ] = 1 NEW_LINE DEDENT if ( s - d1 not in visited ) : NEW_LINE INDENT q . appendleft ( [ ( s - d1 ) , stp + 1 ] ) NEW_LINE visited [ ( s - d1 ) ] = 1 NEW_LINE DEDENT if ( s - d2 not in visited ) : NEW_LINE INDENT q . appendleft ( [ ( s - d2 ) , stp + 1 ] ) NEW_LINE visited [ ( s - d2 ) ] = 1 NEW_LINE DEDENT DEDENT DEDENT k = 10 NEW_LINE d1 = 4 NEW_LINE d2 = 6 NEW_LINE x = 8 NEW_LINE print ( minStepsNeeded ( k , d1 , d2 , x ) ) NEW_LINE