Tuesday, 26 Oct 2021

# 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:Input: X = 10, D = 3, T = 6Output: YESExplanation: Below are the moves applied-X = X – 3 = 7X = X – 3 = 4X = X – 1 = 3X = X – 1 = 2X = X – 1 = 1X = X – 1 = 0Hence it is possible to make X = 0 after exactly T moves.Input: X = 10, D = 3, T = 5Output: NONaive 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 DSo 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 – TFor a valid answer to exist, (X – T) should be divisible by (D – 1)Below is the implementation of the above approach:C++#include using namespace std;  int possibleReachingSequence(int X, int D, int T){        if (X < T) {        cout