Given arr[] of 5 integers denoting the values of X+Y, X−Y, X*Y, X%Y and ⌊X/Y⌋ in sorted order for two non-zero integers X and Y, the task is to find the value of X and Y.
Note: If no solution exists return two 0s
Examples:
Input: -1, 0, 4, 9, 20
Output: X = 4, Y = 5
Explanation: If we consider, X + Y = 9, X – Y = -1.
Then X and Y are 4 and 5, which satisfies the condition
X * Y = 20, X % Y = 4, Floor(X / Y) = 0.Input: -3, -1, 0, 2, 2
Output: X = -2, Y = -1
Approach: The problem can be solved based on the following mathematical observation
If we have X+Y and X-Y we can find X and Y.
X = [(X+Y)+(X-Y)]/2
Y = X+Y-X
To implement the above idea try all possible pairs of values for X+Y and X-Y using backtracking. Follow the below steps to solve the problem:
- Consider the array elements as A, B, C, D, E
- Try all possible pairs for the value of X+Y and X-Y.
- Find X and Y from those two values based on the above observation.
- If those two values of X and Y satisfy the other values, then return.
- Otherwise, try for another pair.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> #define ll long long using namespace std; // Function to check if X and Y // are valid or not pair<ll, ll> isValid(ll A, ll B, ll C, ll D, ll E) { // a represents 2*a for now ll a = A + B; // 2a/2 = a that must be integer if ( ceil ( float (a / 2)) != floor ( float (a / 2))) { return make_pair(0, 0); } else { // Find value of a a = a / 2; // Find value of b ll b = A - a; // Edge Cases if (a == 0 || b == 0) return make_pair(0, 0); else if ((a + b) > pow (10, 3) || (a - b) < pow (-10, 3)) return make_pair(0, 0); // 1st Condition, C = a*b else if ((a * b == C) && (a / b == D) && (a % b == E) || (a * b == C) && (a / b == E) && (a % b == D)) return make_pair(a, b); // 2nd Condition, D = a*b else if ((a * b == D) && (a / b == C) && (a % b == E) || (a * b == D) && (a / b == E) && (a % b == C)) return make_pair(a, b); // 3rd Condition, E = a*b else if ((a * b == E) && (a / b == C) && (a % b == D) || (a * b == E) && (a / b == D) && (a % b == C)) return make_pair(a, b); // Pairs are not valid then return 0 else return make_pair(0, 0); } } // Function to find two integers X and Y void findNum(ll* arr) { pair<ll, ll> p; bool flag = 0; for ( int i = 0; i <= 4; i++) { // Swapping for every // X + Y combination swap(arr[0], arr[i]); for ( int j = 1; j <= 4; j++) { // Swapping for every // X - Y combination swap(arr[1], arr[j]); // Checking for valid X and Y p = isValid(arr[0], arr[1], arr[2], arr[3], arr[4]); // If both are not -1 then // we found X and Y if ((p.first != 0) && (p.second != 0)) { // Set Flag = true flag = 1; // Print the values in order // i.e., X and Y cout << p.first << " " << p.second << endl; } // Backtracking swap(arr[1], arr[j]); // X and Y are found if (flag) break ; } // Backtracking swap(arr[0], arr[i]); // X and Y are found if (flag) break ; } // If flag is 0 then X and Y // can't be possible if (!flag) cout << 0 << " " << 0 << endl; } // Driver Code int main() { int N = 5; ll arr[N] = { -1, 0, 4, 9, 20 }; // Function call findNum(arr); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to check if X and Y // are valid or not public static long [] isValid( long A, long B, long C, long D, long E) { // a represents 2*a for now long a = A + B; // 2a/2 = a that must be integer if (Math.ceil((a / 2.0 )) != Math.floor((a / 2.0 ))) { long ans[] = { 0 , 0 }; return ans; } else { // Find value of a a = a / 2 ; // Find value of b long b = A - a; long res[] = { 0 , 0 }; long res1[] = { a, b }; // Edge Cases if (a == 0 || b == 0 ) return res; else if ((a + b) > Math.pow( 10 , 3 ) || (a - b) < Math.pow(- 10 , 3 )) return res; // 1st Condition, C = a*b else if ((a * b == C) && (a / b == D) && (a % b == E) || (a * b == C) && (a / b == E) && (a % b == D)) return res1; // 2nd Condition, D = a*b else if ((a * b == D) && (a / b == C) && (a % b == E) || (a * b == D) && (a / b == E) && (a % b == C)) return res1; // 3rd Condition, E = a*b else if ((a * b == E) && (a / b == C) && (a % b == D) || (a * b == E) && (a / b == D) && (a % b == C)) return res1; // Pairs are not valid then return 0 else return res; } } // Function to find two integers X and Y public static void findNum( long arr[]) { long p[] = new long [ 2 ]; int flag = 0 ; for ( int i = 0 ; i <= 4 ; i++) { // Swapping for every // X + Y combination long tmp = arr[ 0 ]; arr[ 0 ] = arr[i]; arr[i] = tmp; for ( int j = 1 ; j <= 4 ; j++) { // Swapping for every // X - Y combination tmp = arr[ 1 ]; arr[ 1 ] = arr[j]; arr[j] = tmp; // Checking for valid X and Y p = isValid(arr[ 0 ], arr[ 1 ], arr[ 2 ], arr[ 3 ], arr[ 4 ]); // If both are not -1 then // we found X and Y if ((p[ 0 ] != 0 ) && (p[ 1 ] != 0 )) { // Set Flag = true flag = 1 ; // Print the values in order // i.e., X and Y System.out.println(p[ 0 ] + " " + p[ 1 ]); } // Backtracking tmp = arr[ 1 ]; arr[ 1 ] = arr[j]; arr[j] = tmp; // X and Y are found if (flag != 0 ) break ; } // Backtracking tmp = arr[ 0 ]; arr[ 0 ] = arr[i]; arr[i] = tmp; // X and Y are found if (flag != 0 ) break ; } // If flag is 0 then X and Y // can't be possible if (flag == 0 ) System.out.println( "0 0" ); } public static void main(String[] args) { int N = 5 ; long arr[] = { - 1 , 0 , 4 , 9 , 20 }; // Function call findNum(arr); } } // This code is contributed by Rohit Pradhan |
Python3
# Python program for above approach import math # Function to check if X and Y # are valid or not def isValid(A, B, C, D, E) : # a represents 2*a for now a = A + B # 2a/2 = a that must be integer if (math.ceil((a / 2.0 )) ! = math.floor((a / 2.0 ))) : ans = [ 0 , 0 ] return ans else : # Find value of a a = a / / 2 # Find value of b b = A - a res = [ 0 , 0 ] res1 = [ a, b ] # Edge Cases if (a = = 0 or b = = 0 ) : return res elif ((a + b) > pow ( 10 , 3 ) or (a - b) < pow ( - 10 , 3 )) : return res # 1st Condition, C = a*b elif ((a * b = = C) and (a / / b = = D) and (a % b = = E) or (a * b = = C) and (a / / b = = E) and (a % b = = D)) : return res1 # 2nd Condition, D = a*b elif ((a * b = = D) and (a / / b = = C) and (a % b = = E) or (a * b = = D) and (a / / b = = E) and (a % b = = C)) : return res1 # 3rd Condition, E = a*b elif ((a * b = = E) and (a / / b = = C) and (a % b = = D) or (a * b = = E) and (a / / b = = D) and (a % b = = C)) : return res1 # Pairs are not valid then return 0 else : return res # Function to find two integers X and Y def findNum(arr) : p = [ 0 ] * 2 flag = 0 for i in range ( 0 , 5 , 1 ) : # Swapping for every # X + Y combination tmp = arr[ 0 ] arr[ 0 ] = arr[i] arr[i] = tmp for j in range ( 1 , 5 , 1 ) : # Swapping for every # X - Y combination tmp = arr[ 1 ] arr[ 1 ] = arr[j] arr[j] = tmp # Checking for valid X and Y p = isValid(arr[ 0 ], arr[ 1 ], arr[ 2 ], arr[ 3 ], arr[ 4 ]) # If both are not -1 then # we found X and Y if ((p[ 0 ] ! = 0 ) and (p[ 1 ] ! = 0 )) : # Set Flag = true flag = 1 # Print the values in order # i.e., X and Y print (p[ 0 ], end = " " ) print (p[ 1 ]) # Backtracking tmp = arr[ 1 ] arr[ 1 ] = arr[j] arr[j] = tmp # X and Y are found if (flag ! = 0 ) : break # Backtracking tmp = arr[ 0 ] arr[ 0 ] = arr[j] arr[i] = tmp # X and Y are found if (flag ! = 0 ) : break # If flag is 0 then X and Y # can't be possible if (flag = = 0 ) : print ( "0 0" ) # Driver code if __name__ = = "__main__" : N = 5 arr = [ - 1 , 0 , 4 , 9 , 20 ] # Function call findNum(arr) # This code is contributed by code_hunt. |
C#
// C# code to implement the approach using System; public class GFG{ // Function to check if X and Y // are valid or not static long [] isValid( long A, long B, long C, long D, long E) { // a represents 2*a for now long a = A + B; // 2a/2 = a that must be integer if (Math.Ceiling((a / 2.0)) != Math.Floor((a / 2.0))) { long [] ans = { 0, 0 }; return ans; } else { // Find value of a a = a / 2; // Find value of b long b = A - a; long [] res = { 0, 0 }; long [] res1 = { a, b }; // Edge Cases if (a == 0 || b == 0) return res; else if ((a + b) > Math.Pow(10, 3) || (a - b) < Math.Pow(-10, 3)) return res; // 1st Condition, C = a*b else if ((a * b == C) && (a / b == D) && (a % b == E) || (a * b == C) && (a / b == E) && (a % b == D)) return res1; // 2nd Condition, D = a*b else if ((a * b == D) && (a / b == C) && (a % b == E) || (a * b == D) && (a / b == E) && (a % b == C)) return res1; // 3rd Condition, E = a*b else if ((a * b == E) && (a / b == C) && (a % b == D) || (a * b == E) && (a / b == D) && (a % b == C)) return res1; // Pairs are not valid then return 0 else return res; } } // Function to find two integers X and Y static void findNum( long [] arr) { long [] p = new long [2]; int flag = 0; for ( int i = 0; i <= 4; i++) { // Swapping for every // X + Y combination long tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; for ( int j = 1; j <= 4; j++) { // Swapping for every // X - Y combination tmp = arr[1]; arr[1] = arr[j]; arr[j] = tmp; // Checking for valid X and Y p = isValid(arr[0], arr[1], arr[2], arr[3], arr[4]); // If both are not -1 then // we found X and Y if ((p[0] != 0) && (p[1] != 0)) { // Set Flag = true flag = 1; // Print the values in order // i.e., X and Y Console.WriteLine(p[0] + " " + p[1]); } // Backtracking tmp = arr[1]; arr[1] = arr[j]; arr[j] = tmp; // X and Y are found if (flag != 0) break ; } // Backtracking tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; // X and Y are found if (flag != 0) break ; } // If flag is 0 then X and Y // can't be possible if (flag == 0) Console.WriteLine( "0 0" ); } static public void Main (){ long [] arr = { -1, 0, 4, 9, 20 }; // Function call findNum(arr); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approach // Function to check if X and Y // are valid or not function isValid(A, B, C, D, E) { // a represents 2*a for now let a = A + B; // 2a/2 = a that must be integer if (Math.ceil((a / 2)) != Math.floor((a / 2))) { let ans = [ 0, 0 ]; return ans; } else { // Find value of a a = Math.floor(a / 2); // Find value of b let b = A - a; let res = [ 0, 0 ]; let res1 = [ a, b ]; // Edge Cases if (a == 0 || b == 0) return res; else if ((a + b) > Math.pow(10, 3) || (a - b) < Math.pow(-10, 3)) return res; // 1st Condition, C = a*b else if ((a * b == C) && (Math.floor(a / b) == D) && (a % b == E) || (a * b == C) && (Math.floor(a / b) == E) && (a % b == D)) return res1; // 2nd Condition, D = a*b else if ((a * b == D) && (Math.floor(a / b) == C) && (a % b == E) || (a * b == D) && (Math.floor(a / b) == E) && (a % b == C)) return res1; // 3rd Condition, E = a*b else if ((a * b == E) && (Math.floor(a / b) == C) && (a % b == D) || (a * b == E) && (Math.floor(a / b) == D) && (a % b == C)) return res1; // Pairs are not valid then return 0 else return res; } } // Function to find two integers X and Y function findNum(arr) { let p = new Array(2); let flag = 0; for (let i = 0; i <= 4; i++) { // Swapping for every // X + Y combination let tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; for (let j = 1; j <= 4; j++) { // Swapping for every // X - Y combination tmp = arr[1]; arr[1] = arr[j]; arr[j] = tmp; // Checking for valid X and Y p = isValid(arr[0], arr[1], arr[2], arr[3], arr[4]); // If both are not -1 then // we found X and Y if ((p[0] != 0) && (p[1] != 0)) { // Set Flag = true flag = 1; // Print the values in order // i.e., X and Y document.write(p[0] + " " + p[1]); } // Backtracking tmp = arr[1]; arr[1] = arr[j]; arr[j] = tmp; // X and Y are found if (flag != 0) break ; } // Backtracking tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; // X and Y are found if (flag != 0) break ; } // If flag is 0 then X and Y // can't be possible if (flag == 0) document.write( "0 0" ); } // Driver code let N = 5; let arr = [ -1, 0, 4, 9, 20 ]; // Function call findNum(arr); // This code is contributed by sanjoy_62. </script> |
4 5
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!