Comprobar si es posible llegar a un número haciendo saltos de dos longitudes dadas

Dada una posición inicial ‘k’ y dos tamaños de salto ‘d1’ y ‘d2’, nuestra tarea es encontrar el número mínimo de saltos necesarios para llegar a ‘x’ si es posible.
En cualquier posición P, podemos saltar a las posiciones: 
 

• P + d1 y P – d1
• P + d2 y P – d2

Ejemplos: 
 

Input : k = 10, d1 = 4, d2 = 6 and x = 8 
Output : 2
1st step 10 + d1 = 14
2nd step 14 - d2 = 8

Input : k = 10, d1 = 4, d2 = 6 and x = 9
Output : -1
-1 indicates it is not possible to reach x.

En el artículo anterior discutimos una estrategia para verificar si K puede alcanzar una lista de números al hacer saltos de dos longitudes dadas. 
Aquí, en lugar de una lista de números, se nos da un solo número entero x y si es accesible desde k , entonces la tarea es encontrar el número mínimo de pasos o saltos necesarios. 
Resolveremos esto usando Breadth first Search : 
Approach : 
 

• Compruebe si se puede acceder a ‘x’ desde k . El número x es accesible desde k si satisface (x – k) % mcd(d1, d2) = 0 .
• Si x es alcanzable: 
  1. Mantenga una tabla hash para almacenar las posiciones ya visitadas.
  2. Aplicar el algoritmo bfs a partir de la posición k.
  3. Si alcanza la posición P en pasos ‘stp’, puede alcanzar la posición p+d1 en pasos ‘stp+1’.
  4. Si la posición P es la posición requerida ‘x’, entonces los pasos tomados para llegar a P son la respuesta

La siguiente imagen muestra cómo el algoritmo encuentra el número de pasos necesarios para llegar a x = 8 con k = 10, d1 = 4 y d2 = 6. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

#include <bits/stdc++.h>
using namespace std;
 
// Function to perform BFS traversal to
// find minimum number of step needed
// to reach x from K
int minStepsNeeded(int k, int d1, int d2, int x)
{
    // Calculate GCD of d1 and d2
    int gcd = __gcd(d1, d2);
 
    // If position is not reachable
    // return -1
    if ((k - x) % gcd != 0)
        return -1;
 
    // Queue for BFS
    queue<pair<int, int> > q;
 
    // Hash Table for marking
    // visited positions
    unordered_set<int> visited;
 
    // we need 0 steps to reach K
    q.push({ k, 0 });
 
    // Mark starting position
    // as visited
    visited.insert(k);
 
    while (!q.empty()) {
 
        int s = q.front().first;
 
        // stp is the number of steps
        // to reach position s
        int stp = q.front().second;
 
        if (s == x)
            return stp;
 
        q.pop();
 
        if (visited.find(s + d1) == visited.end()) {
 
            // if position not visited
            // add to queue and mark visited
            q.push({ s + d1, stp + 1 });
 
            visited.insert(s + d1);
        }
 
        if (visited.find(s + d2) == visited.end()) {
            q.push({ s + d2, stp + 1 });
            visited.insert(s + d2);
        }
 
        if (visited.find(s - d1) == visited.end()) {
            q.push({ s - d1, stp + 1 });
            visited.insert(s - d1);
        }
        if (visited.find(s - d2) == visited.end()) {
            q.push({ s - d2, stp + 1 });
            visited.insert(s - d2);
        }
    }
}
 
// Driver Code
int main()
{
    int k = 10, d1 = 4, d2 = 6, x = 8;
 
    cout << minStepsNeeded(k, d1, d2, x);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
static int __gcd(int a, int b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
     
}
// Function to perform BFS traversal to
// find minimum number of step needed
// to reach x from K
static int minStepsNeeded(int k, int d1,
                          int d2, int x)
{
    // Calculate GCD of d1 and d2
    int gcd = __gcd(d1, d2);
 
    // If position is not reachable
    // return -1
    if ((k - x) % gcd != 0)
        return -1;
 
    // Queue for BFS
    Queue<pair> q = new LinkedList<>();
 
    // Hash Table for marking
    // visited positions
    HashSet<Integer> visited = new HashSet<>();
 
    // we need 0 steps to reach K
    q.add(new pair(k, 0 ));
 
    // Mark starting position
    // as visited
    visited.add(k);
 
    while (!q.isEmpty())
    {
        int s = q.peek().first;
 
        // stp is the number of steps
        // to reach position s
        int stp = q.peek().second;
 
        if (s == x)
            return stp;
 
        q.remove();
 
        if (!visited.contains(s + d1))
        {
 
            // if position not visited
            // add to queue and mark visited
            q.add(new pair(s + d1, stp + 1));
 
            visited.add(s + d1);
        }
 
        if (visited.contains(s + d2))
        {
            q.add(new pair(s + d2, stp + 1));
            visited.add(s + d2);
        }
 
        if (!visited.contains(s - d1))
        {
            q.add(new pair(s - d1, stp + 1));
            visited.add(s - d1);
        }
        if (!visited.contains(s - d2))
        {
            q.add(new pair(s - d2, stp + 1));
            visited.add(s - d2);
        }
    }
    return Integer.MIN_VALUE;
}
 
// Driver Code
public static void main(String[] args)
{
    int k = 10, d1 = 4, d2 = 6, x = 8;
 
    System.out.println(minStepsNeeded(k, d1, d2, x));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
from math import gcd as __gcd
from collections import deque as queue
 
# Function to perform BFS traversal to
# find minimum number of step needed
# to reach x from K
def minStepsNeeded(k, d1, d2, x):
     
    # Calculate GCD of d1 and d2
    gcd = __gcd(d1, d2)
 
    # If position is not reachable
    # return -1
    if ((k - x) % gcd != 0):
        return -1
 
    # Queue for BFS
    q = queue()
 
    # Hash Table for marking
    # visited positions
    visited = dict()
 
    # we need 0 steps to reach K
    q.appendleft([k, 0])
 
    # Mark starting position
    # as visited
    visited[k] = 1
 
    while (len(q) > 0):
 
        sr = q.pop()
        s, stp = sr[0], sr[1]
 
        # stp is the number of steps
        # to reach position s
        if (s == x):
            return stp
 
        if (s + d1 not in visited):
 
            # if position not visited
            # add to queue and mark visited
            q.appendleft([(s + d1), stp + 1])
 
            visited[(s + d1)] = 1
 
        if (s + d2 not in visited):
            q.appendleft([(s + d2), stp + 1])
            visited[(s + d2)] = 1
 
        if (s - d1 not in visited):
            q.appendleft([(s - d1), stp + 1])
            visited[(s - d1)] = 1
 
        if (s - d2 not in visited):
            q.appendleft([(s - d2), stp + 1])
            visited[(s - d2)] = 1
 
# Driver Code
k = 10
d1 = 4
d2 = 6
x = 8
 
print(minStepsNeeded(k, d1, d2, x))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;            
     
class GFG
{
public class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
static int __gcd(int a, int b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
     
}
 
// Function to perform BFS traversal to
// find minimum number of step needed
// to reach x from K
static int minStepsNeeded(int k, int d1,
                          int d2, int x)
{
    // Calculate GCD of d1 and d2
    int gcd = __gcd(d1, d2);
 
    // If position is not reachable
    // return -1
    if ((k - x) % gcd != 0)
        return -1;
 
    // Queue for BFS
    Queue<pair> q = new Queue<pair>();
 
    // Hash Table for marking
    // visited positions
    HashSet<int> visited = new HashSet<int>();
 
    // we need 0 steps to reach K
    q.Enqueue(new pair(k, 0));
 
    // Mark starting position
    // as visited
    visited.Add(k);
 
    while (q.Count != 0)
    {
        int s = q.Peek().first;
 
        // stp is the number of steps
        // to reach position s
        int stp = q.Peek().second;
 
        if (s == x)
            return stp;
 
        q.Dequeue();
 
        if (!visited.Contains(s + d1))
        {
 
            // if position not visited
            // add to queue and mark visited
            q.Enqueue(new pair(s + d1, stp + 1));
 
            visited.Add(s + d1);
        }
 
        if (!visited.Contains(s + d2))
        {
            q.Enqueue(new pair(s + d2, stp + 1));
            visited.Add(s + d2);
        }
 
        if (!visited.Contains(s - d1))
        {
            q.Enqueue(new pair(s - d1, stp + 1));
            visited.Add(s - d1);
        }
        if (!visited.Contains(s - d2))
        {
            q.Enqueue(new pair(s - d2, stp + 1));
            visited.Add(s - d2);
        }
    }
    return int.MinValue;
}
 
// Driver Code
public static void Main(String[] args)
{
    int k = 10, d1 = 4, d2 = 6, x = 8;
 
    Console.WriteLine(minStepsNeeded(k, d1, d2, x));
}
}
 
// This code is contributed by PrinciRaj1992

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

2

Complejidad de tiempo:   O(|kx|) 

Espacio Auxiliar: O(|kx|)