Compruebe si X se puede reducir a 0 exactamente en T movimientos restando D o 1 de él

Dado un número entero X , D y T , la tarea es verificar si es posible reducir X a 0 exactamente en T movimientos. En cada movimiento, X se puede reducir en D o en 1. Escriba SÍ si es posible, de lo contrario NO.

Ejemplo:

Entrada: X = 10, D = 3, T = 6
Salida: SÍ
Explicación: A continuación se muestran los movimientos aplicados 
: X = X – 3 = 7
X = X – 3 = 4
X = X – 1 = 3
X = X – 1 = 2
X = X – 1 = 1
X = X – 1 = 0
Por lo tanto, es posible hacer X = 0 después de exactamente T movimientos.

Entrada: X = 10, D = 3, T = 5
Salida: NO

Enfoque ingenuo: verifique los posibles movimientos de reducción de D y 1, y verifique si X se puede hacer a 0 exactamente en T movimientos.
Complejidad del tiempo: O(X)

Enfoque eficiente: el problema dado se puede resolver siguiendo los siguientes pasos:

• Sea K el número de veces que X se reduce en D
• Entonces, la distancia total será K*(D) + (T – K) ,  y debería ser igual a X.
  Por lo tanto la ecuación se convierte en 
   

=> K*(D – 1) + T = X 
=> K*(D – 1) = X – T 
 
 

• Para que exista una respuesta válida, ( X – T ) debe ser divisible por ( D – 1)

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

// C++ Program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check the above problem condition
int possibleReachingSequence(int X, int D, int T)
{
    // Check for base cases
    if (X < T) {
        cout << "NO";
        return 0;
    }
    if (T * D < X) {
        cout << "NO";
        return 0;
    }
    // Check if D - 1 is a divisor of X - T
    if ((X - T) % (D - 1) == 0) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
    return 0;
}
 
// Driver Code
int main()
{
    int X = 10, D = 3, T = 6;
    possibleReachingSequence(X, D, T);
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check the above problem condition
static int possibleReachingSequence(int X, int D, int T)
{
    // Check for base cases
    if (X < T) {
        System.out.println("NO");
        return 0;
    }
    if (T * D < X) {
        System.out.println("NO");
        return 0;
    }
    // Check if D - 1 is a divisor of X - T
    if ((X - T) % (D - 1) == 0) {
        System.out.println("YES");
    }
    else {
        System.out.println("NO");
    }
    return 0;
}
 
 
// Driver Code
public static void main(String args[])
{
    int X = 10, D = 3, T = 6;
    possibleReachingSequence(X, D, T);
}
}

# Python program for the above approach
 
# Function to check the above problem condition
def possibleReachingSequence(X, D, T):
   
  # Check the base case.
  if X < T:
    return "NO"
  if T*D < X:
    return "NO"
   
  # check if X-T is a divisor of D-1
  if (X - T) % (D - 1) == 0:
    return "YES"
  return "NO"
 
# Driver code
X = 10
D = 3
T = 6
print(possibleReachingSequence(X, D, T))
 
# This code is contributed by maddler.

// C# program for the above approach
 
using System;
 
public class GFG{
 
// Function to check the above problem condition
static int possibleReachingSequence(int X, int D, int T)
{
    // Check for base cases
    if (X < T) {
        Console.WriteLine("NO");
        return 0;
    }
    if (T * D < X) {
        Console.WriteLine("NO");
        return 0;
    }
    // Check if D - 1 is a divisor of X - T
    if ((X - T) % (D - 1) == 0) {
        Console.WriteLine("YES");
    }
    else {
        Console.WriteLine("NO");
    }
    return 0;
}
 
 
// Driver Code
public static void Main(string []args)
{
    int X = 10, D = 3, T = 6;
    possibleReachingSequence(X, D, T);
}
}
 
// This code is contributed by AnkThon

<script>
// Javascript Program to implement the above approach
 
// Function to check the above problem condition
function possibleReachingSequence(X, D, T)
{
 
  // Check for base cases
  if (X < T) {
    document.write("NO");
    return 0;
  }
  if (T * D < X) {
    document.write("NO");
    return 0;
  }
   
  // Check if D - 1 is a divisor of X - T
  if ((X - T) % (D - 1) == 0) {
    document.write("YES");
  } else {
    document.write("NO");
  }
  return 0;
}
 
// Driver Code
 
let X = 10,
  D = 3,
  T = 6;
possibleReachingSequence(X, D, T);
 
// This code is contributed by gfgking.
</script>

YES

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)