Achieving Y through integer splitting

Namachila October 13, 2025

0 0 7 minutes read

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., $A = 2*B$ ….. (Equation 1)

The sum of A and B is X, i.e., $A + B = X$ ….. (Equation 2)

Therefore solving the above two equations:

$X = A + B = 2B + B = 3B$ ….. (By Substituting Equation 1 in 2)

Therefore, $B = \frac{X}{3}$ and $A = \frac{2X}{3}$

Hence for splitting X into A and B as per the given conditions, X must be a multiple of 3.

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*B
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
int 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 code
if __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 addition
function 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 code
const X = 9;
const Y = 4;
 
// Function call
if (isYPossibleFromX(X, Y)) {
  console.log("YES");
} else {
  console.log("NO");
}
 
// This code is contributed by Tapesh(tapeshdua420)

Output

YES

Time Complexity: O(2^(log₃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*B
bool 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 code
int 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 approach
import 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 $(log_{3}X)^{2}$
Auxiliary Space: O(X)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!