Given integers X and Y, the task is to check if Y can be formed from X by performing the following operations any number of times:
- Split X into 2 integers A and B such that:
- A is twice B
- The Sum of A and B is equal to X
- Update the value of X with either A or B
- Repeat the above steps till Y is achieved.
Examples:
Input: X = 9, Y = 4
Output: YES
Explanation: The operations can be performed as follows:
- Split X(= 9) into 6 and 3, such that A = 6 and B = 3. (as 6 = 2*3 and 6 + 3 = 9)
- Update X with A, i.e., X = 6
- Now Split X(= 6) into 4 and 2, such that A = 4 and B = 2. (as 4 = 2*2 and 2 + 4 = 6)
Therefore Y = 4 has been achieved after 2 operations. So print YES.
Input : X = 4, Y = 2
Output : NO
Explanation : It can be guaranteed that X = 4 cannot be further broken down into A and B such that it follows the given condition
Approach: To solve this problem, let us first see an observation:
Given that X is split into A and B, such that:
- A is twice B, i.e.,
….. (Equation 1)
- The sum of A and B is X, i.e.,
….. (Equation 2)
Therefore solving the above two equations:
….. (By Substituting Equation 1 in 2)
- Therefore,
and
Hence for splitting X into A and B as per the given conditions, X must be a multiple of 3.
….. (Equation 1)
….. (Equation 2)
Now based on this observation, The problem can be solved easily by using Recursion. Following steps can be used to arrive at the solution:
- Case 1: If X is already equal to Y,
- Integer Y is feasible always, without doing any operations. Hence return YES
- Case 2: If X is not divisible by 3,
- it is not possible to arrive at the solution Y, as explained in the above observation. Hence return NO
- Case 3: If X is a multiple of 3,
- Divide X into X/3 and 2*X/3 recursively, and check if constructing Y is possible.
Following is the code based on the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to Check if it is possible to// construct Y from X by splitting it into// two integers A and B such that A=2*Bbool isYPossibleFromX(int X, int Y){ // Case - 1 // X already equal to Y // Return True if (X == Y) { return true; } // Case - 2 // X not divisble by 3, so split // not possible, Return False else if (X % 3 != 0) { return false; } // Case - 3 // Split X into A and B recursively else { return (isYPossibleFromX(X / 3, Y) || isYPossibleFromX(2 * (X / 3), Y)); }}// Driver codeint main(){ int X = 9, Y = 4; // Function call if (isYPossibleFromX(X, Y)) { cout << "YES"; } else { cout << "NO"; } return 0;} |
Java
import java.io.*;public class GFG { // Function to check if it is possible to construct Y from X // by splitting it into two integers A and B such that A=2*B public static boolean isYPossibleFromX(int X, int Y) { // Case - 1 // X already equal to Y // Return true if (X == Y) { return true; } // Case - 2 // X not divisible by 3, so split not possible, return false else if (X % 3 != 0) { return false; } // Case - 3 // Split X into A and B recursively else { return (isYPossibleFromX(X / 3, Y) || isYPossibleFromX(2 * (X / 3), Y)); } } // Driver code public static void main(String[] args) { int X = 9, Y = 4; // Function call if (isYPossibleFromX(X, Y)) { System.out.println("YES"); } else { System.out.println("NO"); } }} |
Python
def is_y_possible_from_x(X, Y): # Case - 1 # X already equal to Y # Return True if X == Y: return True # Case - 2 # X not divisible by 3, so split # not possible, Return False elif X % 3 != 0: return False # Case - 3 # Split X into A and B recursively else: return is_y_possible_from_x(X // 3, Y) or is_y_possible_from_x(2 * (X // 3), Y)# Driver codeif __name__ == "__main__": X = 9 Y = 4 # Function call if is_y_possible_from_x(X, Y): print("YES") else: print("NO") |
C#
using System;class Program{ // Function to Check if it is possible to // construct Y from X by splitting it into // two integers A and B such that A=2*B static bool IsYPossibleFromX(int X, int Y) { // Case - 1 // X already equal to Y // Return True if (X == Y) { return true; } // Case - 2 // X not divisble by 3, so split // not possible, Return False else if (X % 3 != 0) { return false; } // Case - 3 // Split X into A and B recursively else { return (IsYPossibleFromX(X / 3, Y) || IsYPossibleFromX(2 * (X / 3), Y)); } } // Driver code static void Main(string[] args) { int X = 9, Y = 4; if (IsYPossibleFromX(X, Y)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
// Javascript code additionfunction isYPossibleFromX(X, Y) { // Case - 1 // X already equal to Y // Return true if (X === Y) { return true; } // Case - 2 // X not divisible by 3, so split // not possible, Return false else if (X % 3 !== 0) { return false; } // Case - 3 // Split X into A and B recursively else { return isYPossibleFromX(Math.floor(X / 3), Y) || isYPossibleFromX(2 * Math.floor(X / 3), Y); }}// Driver codeconst X = 9;const Y = 4;// Function callif (isYPossibleFromX(X, Y)) { console.log("YES");} else { console.log("NO");}// This code is contributed by Tapesh(tapeshdua420) |
Output
YES
Time Complexity: O(2^(log3 X))
Auxiliary Space: O(1)
Efficient Approach: We can optimize the above recursive approach using memoization. Let us see an observation:
Let’s recursively break X as follow:
- Firstly we break X into A=2X/3 and B=X/3.
- Now, breaking 2X/3 gives us 4X/9 and 2X/9.
- Also, breaking X/3 gives us 2X/9 and X/9.
We can clearly see that 2X/3 is calculated twice. Hence we can use memoization to avoid this recomputation.
Based on the above observation we can clearly see that 2X/3 is calculated twice. Hence we can use memoization to avoid this recomputation.
The following steps can be used to arrive at the solution:
- Initialize an array dp[] of size X+1 with dp[i] = -1 for each 0 < i <= X.
- While each recursive call stores dp[i] = 0(i.e. false) if Y cannot be derived from current X and dp[i] = 1(i.e. true) if Y can be derived from the current X.
- return back from a recursive call if dp[X] != -1(i.e current X is already computed and we can avoid recomputation)
Following is the code based on the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to Check if it is possible to// construct Y from X by splitting it into// two integers A and B such that A = 2*Bbool isYPossibleFromX(int X, int Y, int dp[]){ // Case: when X is already computed // we can return back the already // stored answer if (dp[X] != -1) return dp[X]; // Case -1: we found Y and hence can // return true if (X == Y) { dp[X] = 1; return true; } // Case - 2: We store dp[X]=0 as X is // not divisible by 3 and return false else if (X % 3 != 0) { dp[X] = 0; return false; } // Case - 3: we recursively break X // and store the dp value accordingly else { if (isYPossibleFromX(X / 3, Y, dp) || isYPossibleFromX(2 * (X / 3), Y, dp)) { dp[X] = 1; return true; } else { dp[X] = 0; return false; } }}// Driver codeint main(){ int X = 9, Y = 4; int dp[X + 1]; for (int i = 0; i <= X; i++) { dp[i] = -1; } // Function Call bool answer = isYPossibleFromX(X, Y, dp); if (answer) { cout << "YES"; } else { cout << "NO"; } return 0;} |
Java
// Java code for the above approachimport java.util.Arrays;class Main { // Function to Check if it is possible to // construct Y from X by splitting it into // two integers A and B such that A = 2*B static boolean isYPossibleFromX(int X, int Y, int[] dp) { // Case: when X is already computed // we can return back the already // stored answer if (dp[X] != -1) return dp[X] == 1; // Case -1: we found Y and hence can // return true if (X == Y) { dp[X] = 1; return true; } // Case - 2: We store dp[X]=0 as X is // not divisible by 3 and return false else if (X % 3 != 0) { dp[X] = 0; return false; } // Case - 3: we recursively break X // and store the dp value accordingly else { if (isYPossibleFromX(X / 3, Y, dp) || isYPossibleFromX(2 * (X / 3), Y, dp)) { dp[X] = 1; return true; } else { dp[X] = 0; return false; } } } // Driver code public static void main(String[] args) { int X = 4, Y = 4; int[] dp = new int[X + 1]; Arrays.fill(dp, -1); // Function Call boolean answer = isYPossibleFromX(X, Y, dp); if (answer) { System.out.println("YES"); } else { System.out.println("NO"); } }}// This code is contributed by Sakshi |
Output
YES
Time Complexity: O
Auxiliary Space: O(X)
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!
