Check if X can be reduced to 0 in exactly T moves by subtracting 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 = 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
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> |
YES
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us