Проверьте, можно ли уменьшить X до 0 ровно за T ходов, вычитая из него D или 1.

Даны целые числа X , D и T , задача состоит в том, чтобы проверить, можно ли уменьшить X до 0 ровно за T ходов. На каждом ходу X можно уменьшить либо на D, либо на 1. Если возможно, выведите YES, иначе NO.

Пример:

Input: X = 10, D = 3, T = 6
Output: YES
Explanation: 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 = 5
Output: NO

Наивный подход: проверьте возможные ходы уменьшения D и 1 и проверьте, можно ли сделать X равным 0 ровно за T ходов.
Временная сложность: O(X)

Эффективный подход: данная проблема может быть решена с помощью следующих шагов:

• Пусть K будет количеством раз, когда X уменьшается на D
• Таким образом, общее расстояние будет K*(D) + (T – K) и должно быть равно X.
  Поэтому уравнение становится
  

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

• Чтобы существовал действительный ответ, ( X – T ) должно делиться на ( D – 1)

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)