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 longusing namespace std;// Function to check if X and Y// are valid or notpair<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 Yvoid 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 Codeint main(){ int N = 5; ll arr[N] = { -1, 0, 4, 9, 20 }; // Function call findNum(arr); return 0;} |
Java
// Java code to implement the approachimport 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 approachimport math # Function to check if X and Y# are valid or notdef 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 Ydef 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 codeif __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 approachusing 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> |
Output
4 5
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!
