# Check if X can be reduced to 0 in exactly T moves by substracting D or 1 from it

Given an integer **X**, **D** and **T**, the task is to check if it is possible to reduce X to 0 in exactly T moves. In each move, X can be reduced by either D or 1. Print YES if possible, else NO.

**Example:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:X = 10, D = 3, T = 6Output:YESExplanation:Below are the moves applied-

X = X – 3 = 7

X = X – 3 = 4

X = X – 1 = 3

X = X – 1 = 2

X = X – 1 = 1

X = X – 1 = 0

Hence it is possible to make X = 0 after exactly T moves.

Input:X = 10, D = 3, T = 5Output:NO

**Naive Approach:** Check for possible moves of reducing D and 1, and check if X can be made to 0 in exactly T moves.**Time Complexity: **O(X)

**Efficient Approach:**Given problem can be solved using following steps:

- Let
**K**be the number of times**X**is reduced by**D** - So the total distance will be
**K*(D) + (T – K)**, and it should be equal to**X**.

Therefore the equation becomes

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

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

- For a valid answer to exist, (
**X**–**T**) should be divisible by (**D**– 1)

Below is the implementation of the above approach:

## C++

`// 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

`// 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);` `}` `}` |

## Python3

`# 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#

`// 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` |

## Javascript

`<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>` |

**Output**

YES

**Time Complexity: **O(1)**Auxiliary Space: **O(1)