Comprobar si se puede alcanzar un valor dado desde otro valor en una cola circular mediante saltos de longitud K

Dados los números enteros N , K , A y B , compruebe si es posible llegar a B desde A en una cola circular de números enteros del 1 al N colocados secuencialmente, mediante saltos de longitud K. En cada movimiento, si es posible, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: N = 5, A = 2, B = 1, K = 2
Salida: Sí
Explicación: 2 -> 4 -> 1. Por lo tanto, es posible llegar a B desde A.

Entrada: N = 9, A = 6, B = 5, K = 3
Salida: No

Planteamiento: La idea para resolver el problema se basa en las siguientes observaciones:

• Para la posición A , y después de t pasos , la posición de A es (A + K*t)%N .
• Para la posición B , y después de t pasos , la posición de B es (A + K*t)%N .
• Se puede escribir como:

(A + K*t) = (N*q + B), donde q es cualquier número entero positivo
(A – B) = N*q – K*t

Al observar la ecuación anterior (N*q – K*t) es divisible por MCD de N y K. Por lo tanto, (A – B) también es divisible por MCD de N y K. Por lo tanto, para llegar a B desde A , (A – B) debe ser divisible por MCD(N, K) .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return GCD of two
// numbers a and b
int GCD(int a, int b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively Find the GCD
    return GCD(b, a % b);
}
 
// Function to check of B can be reached
// from A with a jump of K elements in
// the circular queue
void canReach(int N, int A, int B, int K)
{
 
    // Find GCD of N and K
    int gcd = GCD(N, K);
 
    // If A - B is divisible by gcd
    // then print Yes
    if (abs(A - B) % gcd == 0) {
        cout << "Yes";
    }
 
    // Otherwise
    else {
        cout << "No";
    }
}
 
// Driver Code
int main()
{
    int N = 5, A = 2, B = 1, K = 2;
 
    // Function Call
    canReach(N, A, B, K);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class solution{
 
// Function to return GCD
// of two numbers a and b
static int GCD(int a, int b)
{
  // Base Case
  if (b == 0)
    return a;
 
  // Recursively Find
  // the GCD
  return GCD(b, a % b);
}
 
// Function to check of B can
// be reached from A with a jump
// of K elements in the circular
// queue
static void canReach(int N, int A,
                     int B, int K)
{
  // Find GCD of N and K
  int gcd = GCD(N, K);
 
  // If A - B is divisible
  // by gcd then print Yes
  if (Math.abs(A - B) %
      gcd == 0)
  {
    System.out.println("Yes");
  }
 
  // Otherwise
  else
  {
    System.out.println("No");
  }
}
 
// Driver Code
public static void main(String args[])
{
  int N = 5, A = 2,
      B = 1, K = 2;
  // Function Call
  canReach(N, A, B, K);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

# Python3 program for the
# above approach
 
# Function to return GCD
# of two numbers a and b
def GCD(a, b):
   
    # Base Case
    if (b == 0):
        return a
 
    # Recursively Find
    # the GCD
    return GCD(b, a % b)
 
# Function to check of B
# can be reached from A
# with a jump of K elements
# in the circular queue
def canReach(N, A, B, K):
 
    # Find GCD of N and K
    gcd = GCD(N, K)
 
    # If A - B is divisible
    # by gcd then prYes
    if (abs(A - B) %
        gcd == 0):
        print("Yes")
         
    # Otherwise   
    else:
        print("No")
 
# Driver Code
if __name__ == '__main__':
   
    N = 5
    A = 2
    B = 1
    K = 2
 
    # Function Call
    canReach(N, A, B, K)
 
# This code is contributed by Mohit Kumar 29

// C# program for the
// above approach
using System;
 
class GFG{
  
// Function to return GCD
// of two numbers a and b
static int GCD(int a, int b)
{
   
  // Base Case
  if (b == 0)
    return a;
  
  // Recursively Find
  // the GCD
  return GCD(b, a % b);
}
  
// Function to check of B can
// be reached from A with a jump
// of K elements in the circular
// queue
static void canReach(int N, int A,
                     int B, int K)
{
   
  // Find GCD of N and K
  int gcd = GCD(N, K);
  
  // If A - B is divisible
  // by gcd then print Yes
  if (Math.Abs(A - B) % gcd == 0)
  {
    Console.WriteLine("Yes");
  }
  
  // Otherwise
  else
  {
    Console.WriteLine("No");
  }
}
  
// Driver Code
public static void Main()
{
  int N = 5, A = 2,
      B = 1, K = 2;
   
  // Function Call
  canReach(N, A, B, K);
}
}
 
// This code is contributed by code_hunt

<script>
 
// JavaScript program for the above approach
 
// Function to return GCD of two
// numbers a and b
function GCD(a, b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively Find the GCD
    return GCD(b, a % b);
}
 
// Function to check of B can be reached
// from A with a jump of K elements in
// the circular queue
function canReach(N, A, B, K)
{
 
    // Find GCD of N and K
    var gcd = GCD(N, K);
 
    // If A - B is divisible by gcd
    // then print Yes
    if (Math.abs(A - B) % gcd == 0) {
        document.write( "Yes");
    }
 
    // Otherwise
    else {
        document.write( "No");
    }
}
 
// Driver Code
var N = 5, A = 2, B = 1, K = 2;
 
// Function Call
canReach(N, A, B, K);
 
 
</script>

Yes

Complejidad de tiempo: O(log(min(N, K))
Espacio auxiliar: O(1)