Given two positive integers X and Y, the task is to check if X can be converted to Y or not by repeatedly changing the value of X to (3 * X / 2) (if X is even) or (X – 1). If it is possible to convert X into Y, then print “Yes”. Otherwise, print “No”.
Examples:
Input: X = 6, Y = 8
Output: Yes
Explanation:
Operation 1: Convert X(= 6) to 3*X/2 ( = 3 * (6 / 2) = 9).
Operation 2: Convert X(= 9) to (X – 1) (= 8).
Therefore, the total number of operations required is 2.Input: X = 3, Y = 6
Output: No
Approach: The given problem can be solved based on the following observations:
- If the value of X is at least Y, then X can always be converted to Y using the second operation, i.e. reducing X by 1.
- If X is even, then it can be converted to (3 * (X / 2)), which is greater than X for all even numbers greater than 0.
- If the value of X is odd, then X can be converted to (X – 1), which can be converted into (3 * (X – 1)/2), which is greater than X.
- Therefore, from the above observations, the conversion of X into Y is always possible for X > 3.
- Following base cases are required to be considered:
- X = 1: Conversion possible only if Y = 1.
- X = 2 or X = 3: Conversion possible only if Y ? 3.
- In all the other cases, conversion is not possible.
Follow the steps below to solve the problem:
- If the value X is greater than 4, then print “Yes”.
- If the value X is 1 and Y is 1, then print “Yes”.
- If the value X is 2 or 3 and Y is less than 4, then print “Yes”.
- Otherwise, print “No” for all the other cases.
Below is the implementation of above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if X can be// made equal to Y by converting// X to (3*X/2) or (X - 1)void check(int X, int Y){ // Conditions for possible conversion if (X > 3) { cout << "Yes"; } else if (X == 1 and Y == 1) { cout << "Yes"; } else if (X == 2 and Y <= 3) { cout << "Yes"; } else if (X == 3 and Y <= 3) { cout << "Yes"; } // Otherwise, conversion // is not possible else { cout << "No"; }}// Driver Codeint main(){ int X = 6, Y = 8; check(X, Y); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to check if X can be// made equal to Y by converting// X to (3*X/2) or (X - 1)static void check(int X, int Y){ // Conditions for possible conversion if (X > 3) { System.out.print("Yes"); } else if (X == 1 && Y == 1) { System.out.print("Yes"); } else if (X == 2 && Y <= 3) { System.out.print("Yes"); } else if (X == 3 && Y <= 3) { System.out.print("Yes"); } // Otherwise, conversion // is not possible else { System.out.print("No"); }}// Driver Codepublic static void main (String[] args) { int X = 6, Y = 8; check(X, Y);}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to check if X can be# made equal to Y by converting# X to (3*X/2) or (X - 1)def check(X, Y): # Conditions for possible conversion if (X > 3): print("Yes") elif (X == 1 and Y == 1): print("Yes") elif (X == 2 and Y <= 3): print("Yes") elif (X == 3 and Y <= 3): print("Yes") # Otherwise, conversion # is not possible else: print("No")# Driver Codeif __name__ == '__main__': X = 6 Y = 8 check(X, Y)# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;class GFG{// Function to check if X can be// made equal to Y by converting// X to (3*X/2) or (X - 1)static void check(int X, int Y){ // Conditions for possible conversion if (X > 3) { Console.WriteLine("Yes"); } else if (X == 1 && Y == 1) { Console.WriteLine("Yes"); } else if (X == 2 && Y <= 3) { Console.WriteLine("Yes"); } else if (X == 3 && Y <= 3) { Console.WriteLine("Yes"); } // Otherwise, conversion // is not possible else { Console.WriteLine("No"); }}// Driver Codepublic static void Main(string[] args){ int X = 6, Y = 8; check(X, Y);}}// This code is contributed by avijitmondal1998 |
Javascript
<script> // JavaScript program for the above approach // Function to check if X can be // made equal to Y by converting // X to (3*X/2) or (X - 1) function check(X, Y) { // Conditions for possible conversion if (X > 3) { document.write("Yes"); } else if (X == 1 && Y == 1) { document.write("Yes"); } else if (X == 2 && Y <= 3) { document.write("Yes"); } else if (X == 3 && Y <= 3) { document.write("Yes"); } // Otherwise, conversion // is not possible else { document.write("No"); } } let X = 6, Y = 8; check(X, Y);</script> |
Output:
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!